Maximum possible sub-array sum after at most X swaps

0 0 6 minutes read

Given an array arr[] of N integers and an integer X, the task is to find the maximum possible sub-array sum after applying at most X swaps.
Examples:

Input: arr[] = {5, -1, 2, 3, 4, -2, 5}, X = 2
Output: 19
Swap (arr[0], arr[1]) and (arr[5], arr[6]).
Now, the maximum sub-array sum will be (5 + 2 + 3 + 4 + 5) = 19
Input: arr[] = {-2, -3, -1, -10}, X = 10
Output: -1

Approach: For every possible sub-array, consider the elements which are not part of this sub-array as discarded. Now, while there are swaps left and the sum of the sub-array currently under consideration can be maximized i.e. the greatest element among the discarded elements can be swapped with the minimum element of the sub-array, keep updating the sum of the sub-array. When there are no swaps left or the sub-array sum cannot be further maximized, update the current maximum sub-array sum found so far which will be the required answer in the end.
Below is the implementation of the above approach:

CPP

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the maximum
// sub-array sum after at most x swaps
int SubarraySum(int a[], int n, int x)
{
    // To store the required answer
    int ans = -10000;
 
    // For all possible intervals
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
 
            // Keep current ans as zero
            int curans = 0;
 
            // To store the integers which are
            // not part of the sub-array
            // currently under consideration
            priority_queue<int, vector<int> > pq;
 
            // To store elements which are
            // part of the sub-array
            // currently under consideration
            priority_queue<int, vector<int>, greater<int> > pq2;
 
            // Create two sets
            for (int k = 0; k < n; k++) {
                if (k >= i && k <= j) {
                    curans += a[k];
                    pq2.push(a[k]);
                }
                else
                    pq.push(a[k]);
            }
            ans = max(ans, curans);
 
            // Swap at most X elements
            for (int k = 1; k <= x; k++) {
                if (pq.empty() || pq2.empty()
                    || pq2.top() >= pq.top())
                    break;
 
                // Remove the minimum of
                // the taken elements
                curans -= pq2.top();
                pq2.pop();
 
                // Add maximum of the
                // discarded elements
                curans += pq.top();
                pq.pop();
 
                // Update the answer
                ans = max(ans, curans);
            }
        }
    }
 
    // Return the maximized sub-array sum
    return ans;
}
 
// Driver code
int main()
{
    int a[] = { 5, -1, 2, 3, 4, -2, 5 }, x = 2;
    int n = sizeof(a) / sizeof(a[0]);
 
    cout << SubarraySum(a, n, x);
 
    return 0;
}

Java

// Java implementation of the approach 
import java.io.*;
import java.util.*;
class GFG 
{
 
  // Function to return the maximum 
  // sub-array sum after at most x swaps 
  static int SubarraySum(int[] a, int n, int x) 
  {
 
    // To store the required answer 
    int ans = -10000; 
 
    // For all possible intervals 
    for (int i = 0; i < n; i++)
    { 
      for (int j = i; j < n; j++)
      { 
 
        // Keep current ans as zero 
        int curans = 0; 
 
        // To store the integers which are 
        // not part of the sub-array 
        // currently under consideration 
        ArrayList<Integer> pq = new ArrayList<Integer>(); 
 
        // To store elements which are 
        // part of the sub-array 
        // currently under consideration 
        ArrayList<Integer> pq2 = new ArrayList<Integer>(); 
 
        // Create two sets 
        for (int k = 0; k < n; k++) { 
          if (k >= i && k <= j) { 
            curans += a[k]; 
            pq2.add(a[k]); 
          } 
          else
            pq.add(a[k]); 
        }
 
        Collections.sort(pq);
        Collections.reverse(pq);
        Collections.sort(pq2);
 
        ans = Math.max(ans, curans);
 
        // Swap at most X elements 
        for (int k = 1; k <= x; k++) { 
          if (pq.size() == 0 || pq2.size() == 0
              || pq2.get(0) >= pq.get(0)) 
            break; 
 
          // Remove the minimum of 
          // the taken elements 
          curans -= pq2.get(0); 
          pq2.remove(0); 
 
          // Add maximum of the 
          // discarded elements 
          curans += pq.get(0); 
          pq.remove(0); 
 
          // Update the answer 
          ans = Math.max(ans, curans); 
        } 
      } 
    } 
 
    // Return the maximized sub-array sum 
    return ans; 
  }
 
  // Driver code.
  public static void main (String[] args) 
  {
 
    int[] a = { 5, -1, 2, 3, 4, -2, 5 }; 
    int x = 2; 
    int n = a.length;
 
    System.out.println(SubarraySum(a, n, x));
  }
}
 
// This code is contributed by avanitrachhadiya2155

Python3

# Python3 implementation of the approach 
 
# Function to return the maximum 
# sub-array sum after at most x swaps 
def SubarraySum(a, n, x) :
     
    # To store the required answer 
    ans = -10000
     
    # For all possible intervals 
    for i in range(n) :
     
      for j in range(i, n) :
     
        # Keep current ans as zero 
        curans = 0
     
        # To store the integers which are 
        # not part of the sub-array 
        # currently under consideration 
        pq = [] 
     
        # To store elements which are 
        # part of the sub-array 
        # currently under consideration 
        pq2 = []
     
        # Create two sets 
        for k in range(n) :
          if (k >= i and k <= j) :
            curans += a[k]
            pq2.append(a[k]) 
           
          else :
            pq.append(a[k])
     
        pq.sort()
        pq.reverse()
        pq2.sort()
     
        ans = max(ans, curans) 
     
        # Swap at most X elements 
        for k in range(1, x + 1) :
          if (len(pq) == 0 or len(pq2) == 0 or pq2[0] >= pq[0]) :
            break
     
          # Remove the minimum of 
          # the taken elements 
          curans -= pq2[0]
          pq2.pop(0) 
     
          # Add maximum of the 
          # discarded elements 
          curans += pq[0]
          pq.pop(0) 
     
          # Update the answer 
          ans = max(ans, curans)
     
    # Return the maximized sub-array sum 
    return ans
     
    # Driver code
a = [ 5, -1, 2, 3, 4, -2, 5 ]
x = 2; 
n = len(a)
print(SubarraySum(a, n, x))
 
# This code is contributed by divyesh072019.

C#

// C# implementation of the approach 
using System;
using System.Collections.Generic;
class GFG
{
 
  // Function to return the maximum 
  // sub-array sum after at most x swaps 
  static int SubarraySum(int[] a, int n, int x) 
  { 
 
    // To store the required answer 
    int ans = -10000; 
 
    // For all possible intervals 
    for (int i = 0; i < n; i++)
    { 
      for (int j = i; j < n; j++)
      { 
 
        // Keep current ans as zero 
        int curans = 0; 
 
        // To store the integers which are 
        // not part of the sub-array 
        // currently under consideration 
        List<int> pq = new List<int>(); 
 
        // To store elements which are 
        // part of the sub-array 
        // currently under consideration 
        List<int> pq2 = new List<int>(); 
 
        // Create two sets 
        for (int k = 0; k < n; k++) { 
          if (k >= i && k <= j) { 
            curans += a[k]; 
            pq2.Add(a[k]); 
          } 
          else
            pq.Add(a[k]); 
        }
 
        pq.Sort();
        pq.Reverse();
        pq2.Sort();
 
        ans = Math.Max(ans, curans); 
 
        // Swap at most X elements 
        for (int k = 1; k <= x; k++) { 
          if (pq.Count == 0 || pq2.Count == 0 
              || pq2[0] >= pq[0]) 
            break; 
 
          // Remove the minimum of 
          // the taken elements 
          curans -= pq2[0]; 
          pq2.RemoveAt(0); 
 
          // Add maximum of the 
          // discarded elements 
          curans += pq[0]; 
          pq.RemoveAt(0); 
 
          // Update the answer 
          ans = Math.Max(ans, curans); 
        } 
      } 
    } 
 
    // Return the maximized sub-array sum 
    return ans; 
  } 
 
  // Driver code.
  static void Main() {
    int[] a = { 5, -1, 2, 3, 4, -2, 5 }; 
    int x = 2; 
    int n = a.Length;
    Console.WriteLine(SubarraySum(a, n, x));
  }
}
 
// This code is contributed by divyeshrabaiya07.

Javascript

<script>
    // Javascript implementation of the approach
       
    // Function to return the maximum
    // sub-array sum after at most x swaps
    function SubarraySum(a, n, x)
    {
 
      // To store the required answer
      let ans = -10000;
 
      // For all possible intervals
      for (let i = 0; i < n; i++)
      {
        for (let j = i; j < n; j++)
        {
 
          // Keep current ans as zero
          let curans = 0;
 
          // To store the integers which are
          // not part of the sub-array
          // currently under consideration
          let pq = [];
 
          // To store elements which are
          // part of the sub-array
          // currently under consideration
          let pq2 = [];
 
          // Create two sets
          for (let k = 0; k < n; k++) {
            if (k >= i && k <= j) {
              curans += a[k];
              pq2.push(a[k]);
            }
            else
              pq.push(a[k]);
          }
 
          pq.sort();
          pq.reverse();
          pq2.sort();
 
          ans = Math.max(ans, curans);
 
          // Swap at most X elements
          for (let k = 1; k <= x; k++) {
            if (pq.length == 0 || pq2.length == 0
                || pq2[0] >= pq[0])
              break;
 
            // Remove the minimum of
            // the taken elements
            curans -= pq2[0];
            pq2.shift();
 
            // Add maximum of the
            // discarded elements
            curans += pq[0];
            pq.shift();
 
            // Update the answer
            ans = Math.max(ans, curans);
          }
        }
      }
 
      // Return the maximized sub-array sum
      return ans;
    }
       
    let a = [ 5, -1, 2, 3, 4, -2, 5 ];
    let x = 2;
    let n = a.length;
    document.write(SubarraySum(a, n, x)); 
         
        // This code is contributed by suresh07.
</script>

Output:

Time Complexity: O(n³ logn)

Auxiliary Space: O(n)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!