Minimize sum of an Array by swapping a Subarray with another Array
Given two arrays A[] and B[] each of size N, the task is to minimize the sum of an array by swapping a subarray.
Examples:
Input: A[] = {10, 30, 10, 60, 20}, B[] = {40, 10, 40, 30, 10}
Output: 90
Explanation: Swap the subarray {30, 10} with {60, 20}.
The sum of array A[] = 10+30+10+30+10 = 90.
The sum of array B[] = 40+10+40+60+20 = 170.
The minimum sum = 90.
It is the minimum possible sum an array can achieve.Input: A[] = {10, 20, 30}, B[] = {1, 2, 3}
Output: 6
Approach: To problem can be solved based on the following idea:
To minimize the sum of an array, we should swap such a subarray where the difference between the subarray sum is maximum i.e. for array A[] the value of (subarray of A[] – subarray of B[]) is maximum and the same for array B[].
The minimum between these two values will be the answer.To implement this we can create two difference arrays and calculate the largest subarray sum from those difference arrays and subtract them from array sum.
Follow the steps mentioned below to implement the above idea:
- Create two difference arrays (say t[] and s[]) to store the values of (A[i]-B[i]) and (B[i]-A[i]) respectively.
- Calculate the sum of the arrays.
- Now find the maximum subarray sums from t[] and s[] using Kadane’s algorithm.
- Subtract these values from the respective array sum and the minimum between them is the required answer.
Below is the implementation of the above approach.
C++
// C++ code to implement the above approach #include <bits/stdc++.h> using namespace std; // Function to return Max Sum Subarray int maxSubArraySum(vector< int > a) { int max_so_far = INT_MIN, max_ending_here = 0; int size = a.size(); // Loop to find the maximum subarray sum for ( int i = 0; i < size; i++) { max_ending_here = max_ending_here + a[i]; if (max_so_far < max_ending_here) { max_so_far = max_ending_here; } if (max_ending_here < 0) { max_ending_here = 0; } } // Return the maximum subarray sum return max_so_far; } // Function to find Minimum Sum after replacement int findMaxSum(vector< int >& nums1, vector< int >& nums2) { int n = nums1.size(); vector< int > s(n), t(n); // Calculating Sum of nums1 and nums2 int S1 = 0, S2 = 0; for ( int i = 0; i < n; i++) { S1 += nums1[i]; S2 += nums2[i]; } // Creating difference arrays for ( int i = 0; i < n; i++) { t[i] = nums1[i] - nums2[i]; s[i] = nums2[i] - nums1[i]; } // Return Min Sum return min(S2 - maxSubArraySum(s), S1 - maxSubArraySum(t)); } // Driver Code int main() { vector< int > A = { 10, 30, 10, 60, 20 }; vector< int > B = { 40, 10, 40, 30, 10 }; // Function Call cout << findMaxSum(A, B); return 0; } |
Java
// Java code to implement the above approach import java.io.*; class GFG { // Function to return Max Sum Subarray public static int maxSubArraySum( int a[]) { int max_so_far = Integer.MIN_VALUE, max_ending_here = 0 ; int size = a.length; // Loop to find the maximum subarray sum for ( int i = 0 ; i < size; i++) { max_ending_here = max_ending_here + a[i]; if (max_so_far < max_ending_here) { max_so_far = max_ending_here; } if (max_ending_here < 0 ) { max_ending_here = 0 ; } } // Return the maximum subarray sum return max_so_far; } // Function to find Minimum Sum after replacement public static int findMaxSum( int nums1[], int nums2[]) { int n = nums1.length; int s[] = new int [n]; int t[] = new int [n]; // Calculating Sum of nums1 and nums2 int S1 = 0 , S2 = 0 ; for ( int i = 0 ; i < n; i++) { S1 += nums1[i]; S2 += nums2[i]; } // Creating difference arrays for ( int i = 0 ; i < n; i++) { t[i] = nums1[i] - nums2[i]; s[i] = nums2[i] - nums1[i]; } // Return Min Sum return Math.min(S2 - maxSubArraySum(s), S1 - maxSubArraySum(t)); } // Driver Code public static void main(String[] args) { int A[] = { 10 , 30 , 10 , 60 , 20 }; int B[] = { 40 , 10 , 40 , 30 , 10 }; // Function Call System.out.print(findMaxSum(A, B)); } } // This code is contributed by Rohit Pradhan |
Python3
# Python code to implement the above approach # Function to return Max Sum Subarray import sys def maxSubArraySum(a): max_so_far = - sys.maxsize - 1 max_ending_here = 0 size = len (a) # Loop to find the maximum subarray sum for i in range ( 0 ,size): max_ending_here = max_ending_here + a[i] if (max_so_far < max_ending_here): max_so_far = max_ending_here if (max_ending_here < 0 ): max_ending_here = 0 # Return the maximum subarray sum return max_so_far # Function to find Minimum Sum after replacement def findMaxSum(A,B): n = len (A) s = [ 0 ] * n t = [ 0 ] * n # Calculating Sum of s1 and s2 S1 = 0 S2 = 0 for i in range ( 0 ,n): S1 + = A[i] S2 + = B[i] # Creating difference arrays for i in range ( 0 ,n): t[i] = A[i] - B[i] s[i] = B[i] - A[i] # Return Min Sum return min (S2 - maxSubArraySum(s), S1 - maxSubArraySum(t)) # Driver Code A = [ 10 , 30 , 10 , 60 , 20 ] B = [ 40 , 10 , 40 , 30 , 10 ] # Function Call print (findMaxSum(A, B)) # This code is contributed by Atul_kumar_Shrivastava |
C#
using System; public class GFG { // Function to return Max Sum Subarray public static int maxSubArraySum( int [] a) { int max_so_far = Int32.MinValue, max_ending_here = 0; int size = a.Length; // Loop to find the maximum subarray sum for ( int i = 0; i < size; i++) { max_ending_here = max_ending_here + a[i]; if (max_so_far < max_ending_here) { max_so_far = max_ending_here; } if (max_ending_here < 0) { max_ending_here = 0; } } // Return the maximum subarray sum return max_so_far; } // Function to find Minimum Sum after replacement public static int findMaxSum( int [] nums1, int [] nums2) { int n = nums1.Length; int [] s = new int [n]; int [] t = new int [n]; // Calculating sum of nums1 and nums2 int S1 = 0, S2 = 0; for ( int i = 0; i < n; i++) { S1 += nums1[i]; S2 += nums2[i]; } // Creating difference arrays for ( int i = 0; i < n; i++) { t[i] = nums1[i] - nums2[i]; s[i] = nums2[i] - nums1[i]; } // return Min Sum return Math.Min(S2 - maxSubArraySum(s), S1 - maxSubArraySum(t)); } static public void Main() { // Code int [] A = { 10, 30, 10, 60, 20 }; int [] B = { 40, 10, 40, 30, 10 }; // Function call Console.Write(findMaxSum(A, B)); } } // This code is contributed by lokesh (lokeshmvs21). |
Javascript
<script> // JavaScript code to implement the above approach const INT_MIN = -2147483648; // Function to return Max Sum Subarray const maxSubArraySum = (a) => { let max_so_far = INT_MIN, max_ending_here = 0; let size = a.length; // Loop to find the maximum subarray sum for (let i = 0; i < size; i++) { max_ending_here = max_ending_here + a[i]; if (max_so_far < max_ending_here) { max_so_far = max_ending_here; } if (max_ending_here < 0) { max_ending_here = 0; } } // Return the maximum subarray sum return max_so_far; } // Function to find Minimum Sum after replacement const findMaxSum = (nums1, nums2) => { let n = nums1.length; let s = new Array(n).fill(0), t = new Array(n).fill(0); // Calculating Sum of nums1 and nums2 let S1 = 0, S2 = 0; for (let i = 0; i < n; i++) { S1 += nums1[i]; S2 += nums2[i]; } // Creating difference arrays for (let i = 0; i < n; i++) { t[i] = nums1[i] - nums2[i]; s[i] = nums2[i] - nums1[i]; } // Return Min Sum return Math.min(S2 - maxSubArraySum(s), S1 - maxSubArraySum(t)); } // Driver Code let A = [10, 30, 10, 60, 20]; let B = [40, 10, 40, 30, 10]; // Function Call document.write(findMaxSum(A, B)); // This code is contributed by rakeshsahni </script> |
90
Time Complexity: O(N)
Auxiliary Space: O(N)