Maximum Prefix Sum possible by merging two given arrays
Given two arrays A[] and B[] consisting of N and M integers respectively, the task is to calculate the maximum prefix sum that can be obtained by merging the two arrays.
Examples:
Input : A[] = {2, -1, 4, -5}, B[]={4, -3, 12, 4, -3}
Output : 22
Explanation: Merging the two arrays to generate the sequence {2, 4, -1, -3, 4, 12, 4, -5, -3}. Maximum prefix sum = Sum of {arr[0], …, arr[6]} = 22.Input: A[] = {2, 1, 13, 5, 14}, B={-1, 4, -13}
Output: 38
Explanation: Merging the two arrays to generate the sequence {2, 1, -1, 13, 5, 14, -13}. Maximum prefix sum = Sum of {arr[0], …, arr[6]} = 38.
Naive Approach: The simplest approach is to use Recursion, which can be optimized using Memoization. Follow the steps below to solve the problem:
- Initialize a map<pair<int, int>, int> dp[] for memorization.
- Define a recursive function, say maxPresum(x, y) to find the maximum prefix sum:
- If dp[{x, y}] is already calculated, then return dp[{x, y}].
- Otherwise, if x==N || y==M, then return 0.
- Update dp[{x, y}] as dp[{x, y}] = max(dp[{x, y}, a[x]+maxPresum(x+1, y), b[y]+maxPresum(x, y+1)) and then return dp[{x, y}].
- Print the maximum prefix sum as maxPresum(0, 0).
Below is the implementation of the above approach:
C++
// C++ implementation of above approach #include <bits/stdc++.h> #define int long long using namespace std; // Stores the dp states map<pair< int , int >, int > dp; // Recursive Function to calculate the maximum // prefix sum obtained by merging two arrays int maxPreSum(vector< int > a, vector< int > b, int x, int y) { // If subproblem is already computed if (dp.find({ x, y }) != dp.end()) return dp[{ x, y }]; // If x >= N or y >= M if (x == a.size() && y == b.size()) return 0; int curr = dp[{ x, y }]; // If x < N if (x == a.size()) { curr = max(curr, b[y] + maxPreSum(a, b, x, y + 1)); } // If y<M else if (y == b.size()) { curr = max(curr, a[x] + maxPreSum(a, b, x + 1, y)); } // Otherwise else { curr = max({ curr, a[x] + maxPreSum(a, b, x + 1, y), b[y] + maxPreSum(a, b, x, y + 1) }); } return dp[{ x, y }] = curr; } // Driver Code signed main() { vector< int > A = { 2, 1, 13, 5, 14 }; vector< int > B = { -1, 4, -13 }; cout << maxPreSum(A, B, 0, 0) << endl; return 0; } |
Java
import java.util.HashMap; import java.util.Map; public class Main { // Stores the dp states static Map<Tuple, Integer> dp = new HashMap<>(); // Recursive Function to calculate the maximum // prefix sum obtained by merging two arrays static int maxPreSum( int [] a, int [] b, int x, int y) { // If subproblem is already computed if (dp.containsKey( new Tuple(x, y))) { return dp.get( new Tuple(x, y)); } // If x >= N or y >= M if (x == a.length && y == b.length) { return 0 ; } int curr = 0 ; if (dp.containsKey( new Tuple(x, y))) { curr = dp.get( new Tuple(x, y)); } // If x < N if (x == a.length) { curr = Math.max( curr, b[y] + maxPreSum(a, b, x, y + 1 )); } // If y<M else if (y == b.length) { curr = Math.max( curr, a[x] + maxPreSum(a, b, x + 1 , y)); } // Otherwise else { int max = Math.max( a[x] + maxPreSum(a, b, x + 1 , y), b[y] + maxPreSum(a, b, x, y + 1 )); curr = Math.max(curr, max); } dp.put( new Tuple(x, y), curr); return dp.get( new Tuple(x, y)); } // Driver code public static void main(String[] args) { int [] A = { 2 , 1 , 13 , 5 , 14 }; int [] B = { - 1 , 4 , - 13 }; System.out.println(maxPreSum(A, B, 0 , 0 )); } // Tuple class definition static class Tuple { int x; int y; public Tuple( int x, int y) { this .x = x; this .y = y; } @Override public int hashCode() { final int prime = 31 ; int result = 1 ; result = prime * result + x; result = prime * result + y; return result; } @Override public boolean equals(Object obj) { if ( this == obj) { return true ; } if (obj == null ) { return false ; } if (getClass() != obj.getClass()) { return false ; } Tuple other = (Tuple)obj; if (x != other.x) { return false ; } if (y != other.y) { return false ; } return true ; } } } // This code is contributed by phasing17. |
Python3
# Python3 implementation of above approach # Stores the dp states dp = {} # Recursive Function to calculate the maximum # prefix sum obtained by merging two arrays def maxPreSum(a, b, x, y): # If subproblem is already computed if (x, y) in dp: return dp[(x, y)] # If x >= N or y >= M if x = = len (a) and y = = len (b): return 0 ; curr = 0 ; if (x, y) in dp: curr = dp[(x, y)] # If x < N if x = = len (a): curr = max (curr, b[y] + maxPreSum(a, b, x, y + 1 )); # If y<M elif (y = = len (b)): curr = max (curr, a[x] + maxPreSum(a, b, x + 1 , y)); # Otherwise else : maxs = max (a[x] + maxPreSum(a, b, x + 1 , y), b[y] + maxPreSum(a, b, x, y + 1 )); curr = max (curr, maxs); dp[(x, y)] = curr; return dp[(x, y)] # Driver code A = [ 2 , 1 , 13 , 5 , 14 ]; B = [ - 1 , 4 , - 13 ]; print (maxPreSum(A, B, 0 , 0 )); # This code is contributed by phasing17 |
C#
// C# implementation of above approach using System; using System.Collections.Generic; class GFG{ // Stores the dp states static Dictionary<Tuple< int , int >, int > dp = new Dictionary<Tuple< int , int >, int >(); // Recursive Function to calculate the maximum // prefix sum obtained by merging two arrays static int maxPreSum( int [] a, int [] b, int x, int y) { // If subproblem is already computed if (dp.ContainsKey( new Tuple< int , int >(x, y))) return dp[ new Tuple< int , int >(x, y)]; // If x >= N or y >= M if (x == a.Length && y == b.Length) return 0; int curr = 0; if (dp.ContainsKey( new Tuple< int , int >(x, y))) { curr = dp[ new Tuple< int , int >(x, y)]; } // If x < N if (x == a.Length) { curr = Math.Max(curr, b[y] + maxPreSum( a, b, x, y + 1)); } // If y<M else if (y == b.Length) { curr = Math.Max(curr, a[x] + maxPreSum( a, b, x + 1, y)); } // Otherwise else { int max = Math.Max(a[x] + maxPreSum(a, b, x + 1, y), b[y] + maxPreSum(a, b, x, y + 1)); curr = Math.Max(curr, max); } dp[ new Tuple< int , int >(x, y)] = curr; return dp[ new Tuple< int , int >(x, y)]; } // Driver code static void Main() { int [] A = { 2, 1, 13, 5, 14 }; int [] B = { -1, 4, -13 }; Console.WriteLine(maxPreSum(A, B, 0, 0)); } } // This code is contributed by divyesh072019 |
Javascript
// JavaScript implementation of above approach // Stores the dp states const dp = {}; // Recursive Function to calculate the maximum // prefix sum obtained by merging two arrays function maxPreSum(a, b, x, y) { // If subproblem is already computed if (x in dp && y in dp[x]) { return dp[x][y]; } // If x >= N or y >= M if (x === a.length && y === b.length) { return 0; } let curr = 0; if (x in dp && y in dp[x]) { curr = dp[x][y]; } // If x < N if (x === a.length) { curr = Math.max(curr, b[y] + maxPreSum(a, b, x, y + 1)); } // If y<M else if (y === b.length) { curr = Math.max(curr, a[x] + maxPreSum(a, b, x + 1, y)); } // Otherwise else { const maxs = Math.max( a[x] + maxPreSum(a, b, x + 1, y), b[y] + maxPreSum(a, b, x, y + 1) ); curr = Math.max(curr, maxs); } if (!(x in dp)) { dp[x] = {}; } dp[x][y] = curr; return dp[x][y]; } // Driver code const A = [2, 1, 13, 5, 14]; const B = [-1, 4, -13]; console.log(maxPreSum(A, B, 0, 0)); // This code is contributed by phasing17 |
38
Time Complexity: O(N·M)
Auxiliary Space: O(N*M)
Efficient Approach: The above approach can be optimized based on the observation that the maximum prefix sum is equal to the sum of the maximum prefix sum of arrays A[] and B[]. Follow the steps below to solve the problem:
- Calculate the maximum prefix sum of array A[] and store it in a variable, say X.
- Calculate the maximum prefix sum of array B[] and store it in a variable, say Y.
- Print the sum of X and Y.
Below is the implementation of the above approach:
C++
// C++ Program to implement // the above approach #include <bits/stdc++.h> using namespace std; int maxPresum(vector< int > a, vector< int > b) { // Stores the maximum prefix // sum of the array A[] int X = max(a[0], 0); // Traverse the array A[] for ( int i = 1; i < a.size(); i++) { a[i] += a[i - 1]; X = max(X, a[i]); } // Stores the maximum prefix // sum of the array B[] int Y = max(b[0], 0); // Traverse the array B[] for ( int i = 1; i < b.size(); i++) { b[i] += b[i - 1]; Y = max(Y, b[i]); } return X + Y; } // Driver code int main() { vector< int > A = { 2, -1, 4, -5 }; vector< int > B = { 4, -3, 12, 4, -3 }; cout << maxPresum(A, B) << endl; } |
Java
// Java Program to implement // the above approach import java.util.*; class GFG { static int maxPresum( int [] a, int [] b) { // Stores the maximum prefix // sum of the array A[] int X = Math.max(a[ 0 ], 0 ); // Traverse the array A[] for ( int i = 1 ; i < a.length; i++) { a[i] += a[i - 1 ]; X = Math.max(X, a[i]); } // Stores the maximum prefix // sum of the array B[] int Y = Math.max(b[ 0 ], 0 ); // Traverse the array B[] for ( int i = 1 ; i < b.length; i++) { b[i] += b[i - 1 ]; Y = Math.max(Y, b[i]); } return X + Y; } // Driver code public static void main(String [] args) { int [] A = { 2 , - 1 , 4 , - 5 }; int [] B = { 4 , - 3 , 12 , 4 , - 3 }; System.out.print(maxPresum(A, B)); } } // This code is contributed by ukasp. |
Python3
# Python3 implementation of the # above approach def maxPresum(a, b) : # Stores the maximum prefix # sum of the array A[] X = max (a[ 0 ], 0 ) # Traverse the array A[] for i in range ( 1 , len (a)): a[i] + = a[i - 1 ] X = max (X, a[i]) # Stores the maximum prefix # sum of the array B[] Y = max (b[ 0 ], 0 ) # Traverse the array B[] for i in range ( 1 , len (b)): b[i] + = b[i - 1 ] Y = max (Y, b[i]) return X + Y # Driver code A = [ 2 , - 1 , 4 , - 5 ] B = [ 4 , - 3 , 12 , 4 , - 3 ] print (maxPresum(A, B)) # This code is contributed by code_hunt. |
C#
// C# Program to implement // the above approach using System; using System.Collections.Generic; class GFG { static int maxPresum(List< int > a, List< int > b) { // Stores the maximum prefix // sum of the array A[] int X = Math.Max(a[0], 0); // Traverse the array A[] for ( int i = 1; i < a.Count; i++) { a[i] += a[i - 1]; X = Math.Max(X, a[i]); } // Stores the maximum prefix // sum of the array B[] int Y = Math.Max(b[0], 0); // Traverse the array B[] for ( int i = 1; i < b.Count; i++) { b[i] += b[i - 1]; Y = Math.Max(Y, b[i]); } return X + Y; } // Driver code static void Main() { List< int > A = new List< int >( new int []{ 2, -1, 4, -5 }); List< int > B = new List< int >( new int []{ 4, -3, 12, 4, -3 }); Console.WriteLine(maxPresum(A, B)); } } // This code is contributed by divyeshrabadiya07. |
Javascript
<script> // Javascript Program to implement // the above approach function maxPresum(a, b) { // Stores the maximum prefix // sum of the array A[] let X = Math.max(a[0], 0); // Traverse the array A[] for (let i = 1; i < a.length; i++) { a[i] += a[i - 1]; X = Math.max(X, a[i]); } // Stores the maximum prefix // sum of the array B[] let Y = Math.max(b[0], 0); // Traverse the array B[] for (let i = 1; i < b.length; i++) { b[i] += b[i - 1]; Y = Math.max(Y, b[i]); } return X + Y; } let A = [ 2, -1, 4, -5 ]; let B = [ 4, -3, 12, 4, -3 ]; document.write(maxPresum(A, B)); </script> |
22
Time Complexity: O(M+N)
Auxiliary Space: O(1)
Contact Us