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 longusing namespace std;// Stores the dp statesmap<pair<int, int>, int> dp;// Recursive Function to calculate the maximum// prefix sum obtained by merging two arraysint 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 Codesigned 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 statesdp = {}# Recursive Function to calculate the maximum# prefix sum obtained by merging two arraysdef 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 codeA = [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 approachusing System;using System.Collections.Generic;class GFG{ // Stores the dp statesstatic Dictionary<Tuple<int, int>, int> dp = new Dictionary<Tuple<int, int>, int>();// Recursive Function to calculate the maximum// prefix sum obtained by merging two arraysstatic 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 codestatic 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 statesconst dp = {};// Recursive Function to calculate the maximum// prefix sum obtained by merging two arraysfunction 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 codeconst A = [2, 1, 13, 5, 14];const B = [-1, 4, -13];console.log(maxPreSum(A, B, 0, 0));// This code is contributed by phasing17 |
Output:
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 codeint 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 approachdef 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 codeA = [ 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> |
Output:
22
Time Complexity: O(M+N)
Auxiliary Space: O(1)
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!