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 swapsint 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 codeint 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 codea = [ 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:
19
Time Complexity: O(n3 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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
