Given two arrays X[] and Y[] of length N each. You can shift from X[] to Y[] at most once. The task is to output the maximum sum possible sum.
Examples:
Input: N = 4, X[] = {7, 5, 3, 4}, Y[] = {2, 3, 1, 3}
Output: 19
Explanation: It is optimal to not shift from X[] to Y[]. The total maximum possible sum will be 7 + 5 + 3 + 4 = 19.Input: N = 2, X[] = {25, 5}, Y[] = {3, 30}
Output: 55
Explanation: It is optimal to shift after the first index.
Sum at first index= 25
After Shifted from X[] to Y[] after first index sum at second index = 25+Y[2] = 25 + 30 = 55.
It can be verified that sum more than 55 is not possible.
Approach: Implement the idea below to solve the problem
The problem can be solved by using prefix and suffix sum technique. For each index check the prefix sum and suffix sum. If we shift after index i, the sum (say Xi) will be prefix[i] + suffix[i+1].
The maximum value among all the Xi is the maximum possible sum by performing at most 1 shift.
Follow the steps mentioned below to implement the idea:
- Initiate the suffix array of Y[].
- Iterate from i=N-1 to 0 to generate the suffix array.
- Traverse from i = 0 to N:
- Check if the sum of elements in X[] till i and the suffix sum of Y[] from i+1 is greater than the maximum possible sum.
- If it is greater, update the maximum possible.
- Return the maximum possible after the iteration is over.
Code to implement the approach:
C++
// C++ code to implement the approach #include <iostream> using namespace std; // User defined find to maximum from two input arguments int max(int a, int b) { return a >= b ? a : b; } // Function for calculating maximum sum int maximiseSum(int n, int X[], int Y[]) { // Suffix sum array of Y[] int suf[n]; suf[n - 1] = Y[n - 1]; // Variable to store sum of Y[] ans the maximum possible // sum int sum = 0, ans = 0; // Loop for calculating suffix array of Y[] for (int i = n - 2; i >= 0; i--) { sum += Y[i]; suf[i] += suf[i + 1]; } ans = sum; sum = 0; // Loop to find out the maximum possible sum for (int i = 0; i < n - 1; i++) { sum += X[i]; ans = max(ans, sum + suf[i + 1]); } sum += X[n - 1]; ans = max(ans, sum); // Return the answer return ans; } int main() { int N = 4; int X[] = { 7, 5, 3, 4 }; int Y[] = { 2, 3, 1, 3 }; // Function call cout << maximiseSum(N, X, Y); return 0; } // This code is contributed by lokeshmvs21. |
Java
// Java code to implement the approach import java.io.*; import java.lang.*; import java.util.*; class GFG { // Driver Code public static void main(String[] args) { int N = 4; int[] X = { 7, 5, 3, 4 }; int[] Y = { 2, 3, 1, 3 }; // Function Call System.out.println(maximiseSum(N, X, Y)); } // User defined find to maximum // from two input arguments static long max(long a, long b) { return a >= b ? a : b; } // Function for calculating maximum sum static long maximiseSum(int n, int X[], int Y[]) { // Suffix sum array of Y[] long[] suf = new long[n]; suf[n - 1] = Y[n - 1]; // Variable to store sum of Y[] // ans the maximum possible sum long sum = 0, ans = 0; // Loop for calculating suffix array of Y[] for (int i = n - 2; i >= 0; i--) { sum += Y[i]; suf[i] += suf[i + 1]; } ans = sum; sum = 0; // Loop to find out the maximum possible sum for (int i = 0; i < n - 1; i++) { sum += X[i]; ans = max(ans, sum + suf[i + 1]); } sum += X[n - 1]; ans = max(ans, sum); // Return the answer return ans; } } |
Python3
# Python code to implement the approach # Function for calculating maximum sum def maximiseSum(n, X, Y): # Suffix sum array of Y[] suf = [0]*n suf[n - 1] = Y[n - 1] # Variable to store sum of Y[] # ans the maximum possible sum sum = 0 ans = 0 # Loop for calculating suffix array of Y[] for i in range(n-2, -1, -1): sum += Y[i] suf[i] += suf[i + 1] ans = sum sum = 0 # Loop to find out the maximum possible sum for i in range(n-1): sum += X[i] ans = max(ans, sum + suf[i + 1]) sum += X[n - 1] ans = max(ans, sum) # Return the answer return ans N = 4X = [7, 5, 3, 4] Y = [2, 3, 1, 3] print(maximiseSum(N, X, Y)) # This code is contributed by vikkycirus. |
C#
// C# code to implement the approach using System; public class GFG { // Function for calculating maximum sum static long maximiseSum(int n, int[] X, int[] Y) { // Suffix sum array of Y[] long[] suf = new long[n]; suf[n - 1] = Y[n - 1]; // Variable to store sum of Y[] // ans the maximum possible sum long sum = 0, ans = 0; // Loop for calculating suffix array of Y[] for (int i = n - 2; i >= 0; i--) { sum += Y[i]; suf[i] += suf[i + 1]; } ans = sum; sum = 0; // Loop to find out the maximum possible sum for (int i = 0; i < n - 1; i++) { sum += X[i]; ans = max(ans, sum + suf[i + 1]); } sum += X[n - 1]; ans = max(ans, sum); // Return the answer return ans; } // User defined find to maximum // from two input arguments static long max(long a, long b) { return a >= b ? a : b; } static public void Main() { // Code int N = 4; int[] X = { 7, 5, 3, 4 }; int[] Y = { 2, 3, 1, 3 }; // Function Call Console.WriteLine(maximiseSum(N, X, Y)); } } // This code is contributed by lokeshmvs21. |
Javascript
// JavaScript code to implement the approach // User defined find to maximum // from two input arguments function max(a, b){ return a >= b ? a : b; } // Function for calculating maximum sum function maximizeSum(n, X, Y){ // Suffix sum array of Y[] let suf = new Array(); suf[n-1] = Y[n-1]; // Variable to store sum of Y[] // ans the maximum possible sum let sum = 0, ans = 0; // Loop for calculating suffix array of Y[] for (let i = n - 2; i >= 0; i--) { sum += Y[i]; suf[i] += suf[i + 1]; } ans = sum; sum = 0; // Loop to find out the maximum possible sum for (let i = 0; i < n - 1; i++) { sum += X[i]; ans = max(ans, sum + suf[i + 1]); } sum += X[n - 1]; ans = max(ans, sum); // Return the answer return ans; } let N = 4; let X = [ 7, 5, 3, 4 ]; let Y = [ 2, 3, 1, 3 ]; // Function call console.log(maximizeSum(N, X, Y)); // This code is contributed by lokesh. |
Output
19
Time Complexity: O(N)
Auxiliary Space: O(N)
Related Articles:
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!
Share your thoughts in the comments
