Given an array arr[] of size N, the task is to maximize the difference of the sum of elements at even indices and elements at odd indices by shifting any subarray of odd length to the end of the array.
Examples:
Input: arr[] = {1, 2, 3, 4, 5, 6}
Output: 3
Explanation: Initially sum of elements at even indices = 1 + 3 + 5 = 9
Sum of elements at odd indices = 2 + 4 + 6 = 12
Difference = 9 -12 = -3
On shifting the subarray from [0, 2] to the end the array becomes {4, 5, 6, 1, 2, 3}
Sum of elements at even indices = 4 + 6 + 2 = 12
Sum of elements at odd indices = 5 + 1 + 3 = 9
Difference = 12 – 9 = 3
This gives the maximum answer out of all such shifts that is equal to 3.Input: arr[] = {3, 4, 8}
Output: 7
Approach: The task can be solved mathematically, using the prefix sum technique. The problem can be broken down into 4 cases :
Case 1: When length of the array N is even and l (start of subarray) is even {a,b,c,d,e,f} for l = 2, r =4 (one based indexing)
Initial: +a – b + c – d + e -f on shifting sub array of [2,4] to the end the array becomes ={a, e, f, b, c, d}
Final: + a- e +f – b + c-d
On diving the array to 3 subparts [1, l) , [l, r] , (r, N].
The sign of part1 [1, l) remains same, part2 [l, r] remains same and part3 (r, N] becomes negative (opposite sign) after shifting.
If prefix_sum array is computed then sum after shifting becomes
sum1 = prefix_sum(l-1) + ( prefix_sum(r) – prefix_sum(l-1) ) – ((prefix_sum(n) – prefix_sum(r))
sum1 = 2* prefix_sum(r) – prefix_sum(N)Case 2: When length of the array N is even and l (start of subarray) is odd {a, b, c, d, e, f} for l = 3, r = 5(one based indexing)
Initial: +a – b + c – d + e -f on shifting [3,5] to the end the array becomes = {a, b, f, c, d, e}
Final: + a – b + f – c + d – e
On diving the array to 3 subparts [1, l) , [l, r] , (r, N].
The sign of part1 [1, l) remains same, part2 [l, r] becomes opposite sign and part3 (r, N] becomes opposite sign after shifting.
If prefix_sum array is computed then sum after shifting becomes
sum2 = prefix_sum(l-1) – ( prefix_sum(r) – prefix_sum(l-1)) – ((prefix_sum(n) – prefix_sum(r))
sum2 = 2* prefix_sum(l-1) – prefix_sum(N)Case 3: When length of the array N is odd and l (start of subarray) is even {a, b, c, d, e} for l = 2, r = 4 (one based indexing)
Initial: +a – b + c – d + e on shifting sub array of [2,4] to the end the array becomes = {a, e, b, c, d}
Final: + a – e + b – c + d
On diving the array to 3 subparts [1, l) , [l, r] , (r, N].
The sign of part1 [1, l) remains same, part2 [l, r] becomes opposite sign and part3 (r, N] becomes negative(opposite sign) after shifting.
If prefix_sum array is computed then sum after shifting becomes
sum3 = prefix_sum(l-1) – (prefix_sum(r) – prefix_sum(l-1)) – ((prefix_sum(n) – prefix_sum(r))
sum3 = 2* prefix_sum(l-1) – prefix_sum(N)Case 4: When length of the array N is odd and l (start of subarray) is odd {a, b, c, d, e} for l = 3, r =3(one based indexing)
Initial: +a – b + c – d + e on shifting [3,5] to the end the array becomes = {a, b, d, e, c}
Final: + a – b + d – e + c
On diving the array to 3 subparts [1, l) , [l, r] , (r, N].
The sign of part1 [1, l) remains same, part2 [l, r] becomes opposite sign and part3 (r, N] remains same.
If prefix_sum array is computed then sum after shifting becomes
sum4 = prefix_sum(l-1) + (prefix_sum(r) – prefix_sum(l-1)) – ((prefix_sum(n) – prefix_sum(r))
sum4 = 2* prefix_sum(r) – prefix_sum(N)
- If n is even result becomes: max(sum1, sum2).
- If n is odd result becomes: max(sum3,sum4).
Follow the below steps to solve the problem:
- Initialize a vector prefix_sum of size n+1 with 0’s.
- Now modify the odd indices of the array by multiplying them with -1.
- Iterate through the array in the range[1,n] and fill the prefix_sum vector.
- If the size of the array is even
- Initialize the variable maxval to -1e8 to store the max sum.
- Iterate through the prefix sum vector and check
- If i is even assign maxval as max(maxval, 2 * prefix_sum[i] – prefix_sum[n]).
- Else assign maxval as max(maxval, 2 * prefix_sum[i] – prefix_sum[n]).
- If the size of the array is odd.
- Initialize the variable maxval to -1e8 to store the max sum.
- Iterate through the prefix sum vector and check
- If i is even assign maxval as max(maxval, 2 * prefix_sum[i – 1] – prefix_sum[n])
- Else assign maxval as max(maxval, 2 * prefix_sum[i] – prefix_sum[n])
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the maximum value of// difference between sum of elements // at even indices and sum of elements // at odd indices by shifting// a subarray of odd length to the// end of the arrayint find_maxsum(int arr[], int n){ vector<int> prefix_sum(n + 1, 0); // Modify the array to keep // alternative +ve and -ve for (int i = 0; i < n; i++) { if (i % 2 == 1) { arr[i] = -arr[i]; } } // Function to find the prefix sum for (int i = 1; i <= n; i++) { prefix_sum[i] = prefix_sum[i - 1] + arr[i - 1]; } // If n is even if (n % 2 == 0) { // Initialize the maxval to -1e8 int maxval = -1e8; for (int i = 1; i <= n; i++) { // If i is even (case-1) if (i % 2 == 0) { maxval = max(maxval, 2 * prefix_sum[i] - prefix_sum[n]); } // If i is odd (case-2) else { maxval = max(maxval, 2 * prefix_sum[i - 1] - prefix_sum[n]); } } // return the maxval return maxval; } else { // Initialize the maxval to -1e8 int maxval = -1e8; for (int i = 1; i <= n; i++) { // If i is even (case 3) if (i % 2 == 0) { maxval = max(maxval, 2 * prefix_sum[i - 1] - prefix_sum[n]); } // If i is odd (case 4) else { maxval = max(maxval, 2 * prefix_sum[i] - prefix_sum[n]); } } // Return the maxval return maxval; }}int main(){ // Initialize an array int arr[] = { 1, 2, 3, 4, 5, 6 }; int N = sizeof(arr) / sizeof(arr[0]); // Function call cout << find_maxsum(arr, N); return 0;} |
Java
// Java program for the above approachimport java.util.*;public class GFG{ // Function to find the maximum value of // difference between sum of elements // at even indices and sum of elements // at odd indices by shifting // a subarray of odd length to the // end of the array static int find_maxsum(int arr[], int n) { int prefix_sum[] = new int[n + 1]; for(int i = 0; i < n + 1; i++) { prefix_sum[i] = 0; } // Modify the array to keep // alternative +ve and -ve for (int i = 0; i < n; i++) { if (i % 2 == 1) { arr[i] = -arr[i]; } } // Function to find the prefix sum for (int i = 1; i <= n; i++) { prefix_sum[i] = prefix_sum[i - 1] + arr[i - 1]; } // If n is even if (n % 2 == 0) { // Initialize the maxval to -1e8 int maxval = (int)-1e8; for (int i = 1; i <= n; i++) { // If i is even (case-1) if (i % 2 == 0) { maxval = Math.max(maxval, 2 * prefix_sum[i] - prefix_sum[n]); } // If i is odd (case-2) else { maxval = Math.max(maxval, 2 * prefix_sum[i - 1] - prefix_sum[n]); } } // return the maxval return maxval; } else { // Initialize the maxval to -1e8 int maxval = (int)-1e8; for (int i = 1; i <= n; i++) { // If i is even (case 3) if (i % 2 == 0) { maxval = Math.max(maxval, 2 * prefix_sum[i - 1] - prefix_sum[n]); } // If i is odd (case 4) else { maxval = Math.max(maxval, 2 * prefix_sum[i] - prefix_sum[n]); } } // Return the maxval return maxval; } } public static void main(String args[]) { // Initialize an array int arr[] = { 1, 2, 3, 4, 5, 6 }; int N = arr.length; // Function call System.out.println(find_maxsum(arr, N)); }}// This code is contributed by Samim Hossain Mondal. |
Python3
# Python program for the above approach# Function to find the maximum value of# difference between sum of elements # at even indices and sum of elements # at odd indices by shifting# a subarray of odd length to the# end of the arraydef find_maxsum(arr, n): prefix_sum = [ 0 for i in range(n + 1)] # Modify the array to keep # alternative +ve and -ve for i in range(n): if (i % 2 == 1): arr[i] = -arr[i] # Function to find the prefix sum for i in range(1, n+1): prefix_sum[i] = prefix_sum[i - 1] + arr[i - 1] # If n is even if (n % 2 == 0): # Initialize the maxval to -1e8 maxval = -10**8 for i in range(1,n+1): # If i is even (case-1) if (i % 2 == 0): maxval = max(maxval, 2 * prefix_sum[i] - prefix_sum[n]) # If i is odd (case-2) else: maxval = max(maxval, 2 * prefix_sum[i - 1]- prefix_sum[n]) # return the maxval return maxval else: # Initialize the maxval to -1e8 maxval = -10**8 for i in range(1, n+1): # If i is even (case 3) if (i % 2 == 0): maxval = max(maxval, 2 * prefix_sum[i - 1] - prefix_sum[n]) # If i is odd (case 4) else: maxval = max(maxval, 2 * prefix_sum[i] - prefix_sum[n]) # Return the maxval return maxval # Initialize an arrayarr = [1, 2, 3, 4, 5, 6]N = len(arr)# Function callprint(find_maxsum(arr, N))# This code is contributed by Shubham Singh |
C#
// C# code to implement the above approachusing System;public class GFG{ // Function to find the maximum value of // difference between sum of elements // at even indices and sum of elements // at odd indices by shifting // a subarray of odd length to the // end of the array static int find_maxsum(int[] arr, int n) { int[] prefix_sum = new int[n + 1]; for(int i = 0; i < n + 1; i++) { prefix_sum[i] = 0; } // Modify the array to keep // alternative +ve and -ve for (int i = 0; i < n; i++) { if (i % 2 == 1) { arr[i] = -arr[i]; } } // Function to find the prefix sum for (int i = 1; i <= n; i++) { prefix_sum[i] = prefix_sum[i - 1] + arr[i - 1]; } // If n is even if (n % 2 == 0) { // Initialize the maxval to -1e8 int maxval = (int)-1e8; for (int i = 1; i <= n; i++) { // If i is even (case-1) if (i % 2 == 0) { maxval = Math.Max(maxval, 2 * prefix_sum[i] - prefix_sum[n]); } // If i is odd (case-2) else { maxval = Math.Max(maxval, 2 * prefix_sum[i - 1] - prefix_sum[n]); } } // return the maxval return maxval; } else { // Initialize the maxval to -1e8 int maxval = (int)-1e8; for (int i = 1; i <= n; i++) { // If i is even (case 3) if (i % 2 == 0) { maxval = Math.Max(maxval, 2 * prefix_sum[i - 1] - prefix_sum[n]); } // If i is odd (case 4) else { maxval = Math.Max(maxval, 2 * prefix_sum[i] - prefix_sum[n]); } } // Return the maxval return maxval; } } // Driver code public static void Main() { // Initialize an array int[] arr = { 1, 2, 3, 4, 5, 6 }; int N = arr.Length; // Function call Console.Write(find_maxsum(arr, N)); }}// This code is contributed by Shubham Singh |
Javascript
<script>// Javascript program for the above approach// Function to find the maximum value of// difference between sum of elements // at even indices and sum of elements // at odd indices by shifting// a subarray of odd length to the// end of the arrayfunction find_maxsum(arr, n){ let prefix_sum = new Array(n + 1).fill(0); // Modify the array to keep // alternative +ve and -ve for (let i = 0; i < n; i++) { if (i % 2 == 1) { arr[i] = -arr[i]; } } // Function to find the prefix sum for (let i = 1; i <= n; i++) { prefix_sum[i] = prefix_sum[i - 1] + arr[i - 1]; } // If n is even if (n % 2 == 0) { // Initialize the maxval to -1e8 let maxval = -1e8; for (let i = 1; i <= n; i++) { // If i is even (case-1) if (i % 2 == 0) { maxval = Math.max(maxval, 2 * prefix_sum[i] - prefix_sum[n]); } // If i is odd (case-2) else { maxval = Math.max(maxval, 2 * prefix_sum[i - 1] - prefix_sum[n]); } } // return the maxval return maxval; } else { // Initialize the maxval to -1e8 let maxval = -1e8; for (let i = 1; i <= n; i++) { // If i is even (case 3) if (i % 2 == 0) { maxval = Math.max(maxval, 2 * prefix_sum[i - 1] - prefix_sum[n]); } // If i is odd (case 4) else { maxval = Math.max(maxval, 2 * prefix_sum[i] - prefix_sum[n]); } } // Return the maxval return maxval; }}// Initialize an arraylet arr = [1, 2, 3, 4, 5, 6];let N = arr.length;// Function calldocument.write(find_maxsum(arr, N));// This code is contributed by gfgking.</script> |
3
Time Complexity: O(N), as we are using a loop to traverse N times.
Auxiliary Space: O(N), as we are using extra space for prefix_sum.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
