Reverse a subarray to maximize sum of even-indexed elements of given array
Given an array arr[], the task is to maximize the sum of even-indexed elements by reversing a subarray and print the maximum sum obtained.
Examples:
Input: arr[] = {1, 2, 1, 2, 1}
Output: 5
Explanation:
Sum of initial even-indexed elements = a[0] + a[2] + a[4] = 1 + 1 + 1 = 3
Reversing subarray {1, 2, 1, 2} modifies the array to {2, 1, 2, 1, 1}.
Hence, the maximized sum = 2 + 2 + 1 = 5Input: arr[] = {7, 8, 4, 5, 7, 6, 8, 9, 7, 3}
Output: 37
Naive Approach:
The simplest approach to solve the problem is to generate all the possible permutations by reversal of elements one by one and calculate the sum at even indices for each permutation. Print the maximum possible sum among all the permutations.
Time Complexity: O(N3)
Auxiliary Space: O(N)
Efficient Approach:
The above approach can be further optimized to O(N) computational complexity by using Dynamic Programming to check the maximum difference by rotation of arrays.
Follow the steps below to solve the problem:
- Compare the elements at odd index with even index and also keep track of them.
- Initialize two arrays leftDP[] and rightDP[].
- For every odd index, leftDP[] stores the difference of the element at current index with the element on its left and rightDP[] stores that of the right.
- If the difference calculated for the previous index is positive, add it to the current difference:
if(dp[i – 1] > 0)
dp[i] = dp[i-1] + curr_diff
- Otherwise, store the current difference:
dp[i] = curr_diff;
Below is the implementation of the above approach:
C++
// C++ program to implement // the above approach #include <bits/stdc++.h> using namespace std; // Function to return maximized sum // at even indices int maximizeSum( int arr[], int n) { int sum = 0; for ( int i = 0; i < n; i = i + 2) sum += arr[i]; // Stores difference with // element on the left int leftDP[n / 2]; // Stores difference with // element on the right int rightDP[n / 2]; int c = 0; for ( int i = 1; i < n; i = i + 2) { // Compute and store // left difference int leftDiff = arr[i] - arr[i - 1]; // For first index if (c - 1 < 0) leftDP = leftDiff; else { // If previous difference // is positive if (leftDP > 0) leftDP = leftDiff + leftDP; // Otherwise else leftDP[i] = leftDiff; } int rightDiff; // For the last index if (i + 1 >= n) rightDiff = 0; // Otherwise else rightDiff = arr[i] - arr[i + 1]; // For first index if (c - 1 < 0) rightDP = rightDiff; else { // If the previous difference // is positive if (rightDP > 0) rightDP = rightDiff + rightDP; else rightDP = rightDiff; } c++; } int maxi = 0; for ( int i = 0; i < n / 2; i++) { maxi = max(maxi, max(leftDP[i], rightDP[i])); } return maxi + sum; } // Driver Code int main() { int arr[] = { 7, 8, 4, 5, 7, 6, 8, 9, 7, 3 }; int n = sizeof (arr) / sizeof (arr[0]); int ans = maximizeSum(arr, n); cout << (ans); } // This code is contributed by chitranayal |
Java
// Java Program to implement // the above approach import java.io.*; class GFG { // Function to return maximized sum // at even indices public static int maximizeSum( int [] arr) { int n = arr.length; int sum = 0 ; for ( int i = 0 ; i < n; i = i + 2 ) sum += arr[i]; // Stores difference with // element on the left int leftDP[] = new int [n / 2 ]; // Stores difference with // element on the right int rightDP[] = new int [n / 2 ]; int c = 0 ; for ( int i = 1 ; i < n; i = i + 2 ) { // Compute and store // left difference int leftDiff = arr[i] - arr[i - 1 ]; // For first index if (c - 1 < 0 ) leftDP = leftDiff; else { // If previous difference // is positive if (leftDP > 0 ) leftDP = leftDiff + leftDP; // Otherwise else leftDP[i] = leftDiff; } int rightDiff; // For the last index if (i + 1 >= arr.length) rightDiff = 0 ; // Otherwise else rightDiff = arr[i] - arr[i + 1 ]; // For first index if (c - 1 < 0 ) rightDP = rightDiff; else { // If the previous difference // is positive if (rightDP > 0 ) rightDP = rightDiff + rightDP; else rightDP = rightDiff; } c++; } int max = 0 ; for ( int i = 0 ; i < n / 2 ; i++) { max = Math.max(max, Math.max( leftDP[i], rightDP[i])); } return max + sum; } // Driver Code public static void main(String[] args) { int arr[] = { 7 , 8 , 4 , 5 , 7 , 6 , 8 , 9 , 7 , 3 }; int ans = maximizeSum(arr); System.out.println(ans); } } |
Python3
# Python3 program to implement # the above approach # Function to return maximized sum # at even indices def maximizeSum(arr): n = len (arr) sum = 0 for i in range ( 0 , n, 2 ): sum + = arr[i] # Stores difference with # element on the left leftDP = [ 0 ] * (n) # Stores difference with # element on the right rightDP = [ 0 ] * (n) c = 0 for i in range ( 1 , n, 2 ): # Compute and store # left difference leftDiff = arr[i] - arr[i - 1 ] # For first index if (c - 1 < 0 ): leftDP[i] = leftDiff else : # If previous difference # is positive if (leftDP[i] > 0 ): leftDP[i] = (leftDiff + leftDP[i - 1 ]) # Otherwise else : leftDP[i] = leftDiff rightDiff = 0 # For the last index if (i + 1 > = len (arr)): rightDiff = 0 # Otherwise else : rightDiff = arr[i] - arr[i + 1 ] # For first index if (c - 1 < 0 ): rightDP[i] = rightDiff else : # If the previous difference # is positive if (rightDP[i] > 0 ): rightDP[i] = (rightDiff + rightDP[i - 1 ]) else : rightDP[i] = rightDiff c + = 1 maxm = 0 for i in range (n / / 2 ): maxm = max (maxm, max (leftDP[i], rightDP[i])) return maxm + sum # Driver Code if __name__ = = '__main__' : arr = [ 7 , 8 , 4 , 5 , 7 , 6 , 8 , 9 , 7 , 3 ] ans = maximizeSum(arr) print (ans) # This code is contributed by mohit kumar 29 |
C#
// C# program to implement // the above approach using System; class GFG{ // Function to return maximized sum // at even indices public static int maximizeSum( int [] arr) { int n = arr.Length; int sum = 0; for ( int i = 0; i < n; i = i + 2) sum += arr[i]; // Stores difference with // element on the left int []leftDP = new int [n / 2]; // Stores difference with // element on the right int []rightDP = new int [n / 2]; int c = 0; for ( int i = 1; i < n; i = i + 2) { // Compute and store // left difference int leftDiff = arr[i] - arr[i - 1]; // For first index if (c - 1 < 0) leftDP = leftDiff; else { // If previous difference // is positive if (leftDP > 0) leftDP = leftDiff + leftDP; // Otherwise else leftDP = leftDiff; } int rightDiff; // For the last index if (i + 1 >= arr.Length) rightDiff = 0; // Otherwise else rightDiff = arr[i] - arr[i + 1]; // For first index if (c - 1 < 0) rightDP = rightDiff; else { // If the previous difference // is positive if (rightDP > 0) rightDP = rightDiff + rightDP; else rightDP = rightDiff; } c++; } int max = 0; for ( int i = 0; i < n / 2; i++) { max = Math.Max(max, Math.Max(leftDP[i], rightDP[i])); } return max + sum; } // Driver Code public static void Main(String[] args) { int []arr = { 7, 8, 4, 5, 7, 6, 8, 9, 7, 3 }; int ans = maximizeSum(arr); Console.WriteLine(ans); } } // This code is contributed by 29AjayKumar |
Javascript
<script> // Javascript Program to implement // the above approach // Function to return maximized sum // at even indices function maximizeSum(arr) { let n = arr.length; let sum = 0; for (let i = 0; i < n; i = i + 2) sum += arr[i]; // Stores difference with // element on the left let leftDP = new Array(Math.floor(n / 2)); // Stores difference with // element on the right let rightDP = new Array(Math.floor(n / 2)); for (let i=0;i<n/2;i++) { leftDP[i]=0; rightDP[i]=0; } let c = 0; for (let i = 1; i < n; i = i + 2) { // Compute and store // left difference let leftDiff = arr[i] - arr[i - 1]; // For first index if (c - 1 < 0) leftDP[i] = leftDiff; else { // If previous difference // is positive if (leftDP[i] > 0) leftDP[i] = leftDiff + leftDP[i-1]; // Otherwise else leftDP[i] = leftDiff; } let rightDiff; // For the last index if (i + 1 >= arr.length) rightDiff = 0; // Otherwise else rightDiff = arr[i] - arr[i + 1]; // For first index if (c - 1 < 0) rightDP[i] = rightDiff; else { // If the previous difference // is positive if (rightDP[i] > 0) rightDP[i] = rightDiff + rightDP[i-1]; else rightDP[i] = rightDiff; } c++; } let max = 0; for (let i = 0; i < n / 2; i++) { max = Math.max(max, Math.max( leftDP[i], rightDP[i])); } return max + sum; } // Driver Code let arr=[7, 8, 4, 5, 7, 6, 8, 9, 7, 3]; let ans = maximizeSum(arr); document.write(ans); // This code is contributed by avanitrachhadiya2155 </script> |
37
Time Complexity: O(N)
Auxiliary Space: O(N)