Maximum sum of even indexed elements obtained by right shift on an even sized subarray

Last Updated : 29 Oct, 2023

Given an array arr[], we need to find the maximum sum of the even indexed elements that can be obtained by performing right shift operation on any sub-array of even length by 1.

Examples:

Input: arr[] = {5, 1, 3, 4, 5, 6}
Output: 15
Explanation:
We can perform a right shift on index 2 to 5 then resulting array is:
arr[] = {5, 1, 6, 3, 4, 5}
Sum of elements at even indexes = 5 + 6 + 4 = 15
Input: arr[] = {7, 9, 1, 8, 3, 10, 4, 12}
Output: 39
Explanation:
We can perform a right shift on index 0 to 7 then resulting array is:
arr[] = {12, 7, 9, 1, 8, 3, 10, 4}
Sum of elements at even indexes = 12 + 9 + 8 + 10 = 39

Naive Approach: The naive approach is to right shift every possible subarray of even length by one and find the sum of elements at even index for all the array formed after every possible subarray shifts. The maximum sum in all the array is the required result.

Below is the implementation of the above approach:

C++

#include<iostream>
#include<algorithm>
using namespace std;
 
int main(){
    int arr[] = {5, 1, 3, 4, 5, 6};
    int n = sizeof(arr)/sizeof(arr[0]);
    int max_sum = 0;
    for(int i=0; i<n; i+=2){ // iterate over all even indices as starting point
        for(int j=i; j<n; j+=2){ // iterate over all even indices as ending point
            for(int k=i; k<=j; k+=2){ // right shift every even indexed element of subarray by one
                swap(arr[k], arr[k+1]);
            }
            int sum = 0;
            for(int x=0; x<n; x+=2){ // calculate sum of all even indexed elements in resulting array
                sum += arr[x];
            }
            max_sum = max(max_sum, sum); // update max_sum if current sum is greater
            for(int k=i; k<=j; k+=2){ // restore the original array by left shifting the subarray
                swap(arr[k], arr[k+1]);
            }
        }
    }
    cout<<max_sum<<endl;
    return 0;
}
// This code is contributed by rudra1807raj

Java

import java.util.*;
 
public class Main {
    public static void main(String[] args)
    {
        int[] arr = { 5, 1, 3, 4, 5, 6 };
        int n = arr.length;
        int max_sum = 0;
        // iterate over all even indices as starting point
        for (int i = 0; i < n; i += 2) {
            // iterate over all even indices as ending point
            for (int j = i; j < n; j += 2) {
                // right shift every even indexed element of
                // subarray by one
                for (int k = i; k <= j; k += 2) {
                    int temp = arr[k];
                    arr[k] = arr[k + 1];
                    arr[k + 1] = temp;
                }
                int sum = 0;
                // calculate sum of all even indexed
                // elements in resulting array
                for (int x = 0; x < n; x += 2) {
                    sum += arr[x];
                }
                // update max_sum if current sum is greater
                max_sum = Math.max(max_sum, sum);
                // restore the original array by left
                // shifting the subarray
                for (int k = i; k <= j; k += 2) {
                    int temp = arr[k];
                    arr[k] = arr[k + 1];
                    arr[k + 1] = temp;
                }
            }
        }
        System.out.println(max_sum);
    }
}
// This code is contributed by Samim Hossain Mondal.

Python

def main():
    arr = [5, 1, 3, 4, 5, 6]
    n = len(arr)
    max_sum = 0
 
    for i in range(0, n, 2):  # iterate over all even indices as starting point
        for j in range(i, n, 2):  # iterate over all even indices as ending point
            for k in range(i, j+1, 2):  # right shift every even indexed 
                                        # element of subarray by one
                arr[k], arr[k+1] = arr[k+1], arr[k]
             
            sum_even = sum(arr[0::2])  # calculate sum of all even 
                                       # indexed elements in resulting array
            max_sum = max(max_sum, sum_even)  # update max_sum if current sum is greater
             
            for k in range(i, j+1, 2):  # restore the original array by left shifting the subarray
                arr[k], arr[k+1] = arr[k+1], arr[k]
 
    print(max_sum)
 
if __name__ == "__main__":
    main()

C#

using System;
 
class GFG {
    public static void Main(string[] args)
    {
        int[] arr = { 5, 1, 3, 4, 5, 6 };
        int n = arr.Length;
        int max_sum = 0;
        // Iterate over all even indices as the starting
        // point
        for (int i = 0; i < n; i += 2) {
            // Iterate over all even indices as the ending
            // point
            for (int j = i; j < n; j += 2) {
                // Right shift every even indexed element of
                // the subarray by one
                for (int k = i; k <= j; k += 2) {
                    int temp = arr[k];
                    arr[k] = arr[k + 1];
                    arr[k + 1] = temp;
                }
                int sum = 0;
                // Calculate the sum of all even indexed
                // elements in the resulting array
                for (int x = 0; x < n; x += 2) {
                    sum += arr[x];
                }
                // Update max_sum if the current sum is
                // greater
                max_sum = Math.Max(max_sum, sum);
                // Restore the original array by left
                // shifting the subarray
                for (int k = i; k <= j; k += 2) {
                    int temp = arr[k];
                    arr[k] = arr[k + 1];
                    arr[k + 1] = temp;
                }
            }
        }
        Console.WriteLine(max_sum);
    }
}
// This code is contributed by Samim Hossain Mondal.

Javascript

// Nikunj Sonigara
 
function maxEvenSum(arr) {
    const n = arr.length;
    let max_sum = 0;
 
    for (let i = 0; i < n; i += 2) { // Iterate over all even indices as the starting point
        for (let j = i; j < n; j += 2) { // Iterate over all even indices as the ending point
            for (let k = i; k <= j; k += 2) { // Right shift every even indexed element of subarray by one
                [arr[k], arr[k + 1]] = [arr[k + 1], arr[k]];
            }
 
            let sum = 0;
            for (let x = 0; x < n; x += 2) { // Calculate the sum of all even indexed elements in the resulting array
                sum += arr[x];
            }
 
            max_sum = Math.max(max_sum, sum); // Update max_sum if the current sum is greater
 
            for (let k = i; k <= j; k += 2) { // Restore the original array by left shifting the subarray
                [arr[k], arr[k + 1]] = [arr[k + 1], arr[k]];
            }
        }
    }
 
    return max_sum;
}
 
const arr = [5, 1, 3, 4, 5, 6];
const result = maxEvenSum(arr);
console.log(result);

Output

Time Complexity: O(N²)
Auxiliary Space: O(1)

Efficient Approach: To optimized the naive above approach we can observe that after performing the right shift on any even subarray by 1 the odd index value gets replaced by even index value and vice-versa. If we find the sum of element at even indexes(say sum) before shifting, then after shifting the sum gets changed by the sum of the consecutive difference between elements at even and odd index.
For Example:

arr[] = {1, 2, 3, 4}
Sum element at even index in the above array = 1 + 3 = 4
Right shift array by 1, we have
arr1[] = {4, 1, 2, 3}
Sum element at even index in the above array = 4 + 2 = 6
therefore the sum get differ by 2 in the above two array which is equals the sum of consecutive difference in arr[] as ( (2 – 1) + (4 – 3) = 2.

We will use the above concepts to solve this problem. Below are the steps:

Create two arrays(say arr1[] and arr2[]) such that arr1[] will store the consecutive difference of the element in the array arr[] as:

{(a[1] – a[0]), (a[3] – a[2]), . . ., (a[n]-a[n-1])}

And arr2[] will store the consecutive difference of the element in the array arr[] as:

{(a[1] – a[2]), (a[3] – a[4]), . . ., (a[n-1]-a[n])}

Then find the maximum subarray sum using Kadane’s Algorithm in the above two array formed.
Now the maximum sum is the sum of element at even indexes in the original array(arr[]) + maximum subarray sum of the two arrays arr1[] and arr2[].

Below is the implementation of the above approach:

C++

// C++ program for the above approach 
#include <bits/stdc++.h> 
using namespace std; 
 
// Kadane's Algorithm to find 
// the maximum sum sub array 
int kadane(vector<int> v) 
{ 
    int maxSoFar = 0; 
    int maxEndingHere = 0; 
 
    // Iterate array v 
    for (int i = 0; i < v.size(); i++) { 
 
        maxEndingHere += v[i]; 
 
        // Update the maximum 
        maxSoFar = max(maxEndingHere, 
                    maxSoFar); 
 
        // Update maxEndingHere to 0 if it 
        // is less than 0 
        maxEndingHere 
            = max(maxEndingHere, 0); 
    } 
 
    // Return maximum sum 
    return maxSoFar; 
} 
 
// Function to find the sum 
// of even indexed elements 
// after modification in array. 
int sumOfElements(int* arr, int n) 
{ 
    int sum = 0; 
 
    // Find initial sum of 
    // even indexed elements 
    for (int i = 0; i < n; i++) { 
        if (i % 2 == 0) 
            sum += arr[i]; 
    } 
 
    // Create two vectors to store 
    // the consecutive differences 
    // of elements 
    vector<int> v1; 
    vector<int> v2; 
 
    for (int i = 1; i < n; i += 2) { 
 
        v1.push_back(arr[i] 
                    - arr[i - 1]); 
 
        if (i + 1 < n) { 
            v2.push_back(arr[i] 
                        - arr[i + 1]); 
        } 
    } 
 
    // Find the maximum sum subarray 
    int option1 = kadane(v1); 
    int option2 = kadane(v2); 
 
    // Add the maximum value 
    // to initial sum 
    int ans = sum + max(option1, 
                        option2); 
 
    // Return the answer 
    return ans; 
} 
 
// Driver Code 
int main() 
{ 
    // Given array arr[] 
    int arr[] = { 5, 1, 3, 4, 5, 6 }; 
 
    int N = sizeof(arr) / sizeof(arr[0]); 
 
    // Function Call 
    cout << sumOfElements(arr, N); 
    return 0; 
} 

Java

// Java program for the above approach 
import java.util.*; 
 
class GFG{ 
 
// Kadane's Algorithm to find 
// the maximum sum sub array 
static int kadane(Vector<Integer> v) 
{ 
    int maxSoFar = 0; 
    int maxEndingHere = 0; 
 
    // Iterate array v 
    for(int i = 0; i < v.size(); i++) 
    { 
    maxEndingHere += v.get(i); 
         
    // Update the maximum 
    maxSoFar = Math.max(maxEndingHere, 
                        maxSoFar); 
         
    // Update maxEndingHere to 0 if it 
    // is less than 0 
    maxEndingHere = Math.max(maxEndingHere, 0); 
    } 
     
    // Return maximum sum 
    return maxSoFar; 
} 
 
// Function to find the sum 
// of even indexed elements 
// after modification in array. 
static int sumOfElements(int []arr, int n) 
{ 
    int sum = 0; 
 
    // Find initial sum of 
    // even indexed elements 
    for(int i = 0; i < n; i++) 
    { 
    if (i % 2 == 0) 
        sum += arr[i]; 
    } 
 
    // Create two vectors to store 
    // the consecutive differences 
    // of elements 
    Vector<Integer> v1 = new Vector<Integer>(); 
    Vector<Integer> v2 = new Vector<Integer>(); 
 
    for(int i = 1; i < n; i += 2) 
    { 
    v1.add(arr[i] - arr[i - 1]); 
         
    if (i + 1 < n) 
    { 
        v2.add(arr[i] - arr[i + 1]); 
    } 
    } 
     
    // Find the maximum sum subarray 
    int option1 = kadane(v1); 
    int option2 = kadane(v2); 
 
    // Add the maximum value 
    // to initial sum 
    int ans = sum + Math.max(option1, 
                            option2); 
 
    // Return the answer 
    return ans; 
} 
 
// Driver Code 
public static void main(String[] args) 
{ 
     
    // Given array arr[] 
    int arr[] = { 5, 1, 3, 4, 5, 6 }; 
 
    int N = arr.length; 
 
    // Function Call 
    System.out.print(sumOfElements(arr, N)); 
} 
} 
 
// This code is contributed by Amit Katiyar 

Python3

# Python3 program for the above approach 
 
# Kadane's Algorithm to find 
# the maximum sum sub array 
def kadane(v): 
 
    maxSoFar = 0; 
    maxEndingHere = 0; 
 
    # Iterate array v 
    for i in range(len(v)): 
        maxEndingHere += v[i]; 
 
        # Update the maximum 
        maxSoFar = max(maxEndingHere, 
                    maxSoFar); 
 
        # Update maxEndingHere to 0 
        # if it is less than 0 
        maxEndingHere = max(maxEndingHere, 0); 
 
    # Return maximum sum 
    return maxSoFar; 
 
# Function to find the sum 
# of even indexed elements 
# after modification in array. 
def sumOfElements(arr, n): 
 
    sum = 0; 
 
    # Find initial sum of 
    # even indexed elements 
    for i in range(n): 
        if (i % 2 == 0): 
            sum += arr[i]; 
 
    # Create two vectors to store 
    # the consecutive differences 
    # of elements 
    v1 = []; 
    v2 = []; 
 
    for i in range(1, n, 2): 
        v1.append(arr[i] - arr[i - 1]); 
 
        if (i + 1 < n): 
            v2.append(arr[i] - arr[i + 1]); 
 
    # Find the maximum sum subarray 
    option1 = kadane(v1); 
    option2 = kadane(v2); 
 
    # Add the maximum value 
    # to initial sum 
    ans = sum + max(option1, option2); 
 
    # Return the answer 
    return ans; 
 
# Driver Code 
if __name__ == "__main__" : 
 
    # Given array arr[] 
    arr = [ 5, 1, 3, 4, 5, 6 ]; 
 
    N = len(arr); 
 
    # Function call 
    print(sumOfElements(arr, N)); 
 
# This code is contributed by AnkitRai01 

C#

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG{
 
// Kadane's Algorithm to find 
// the maximum sum sub array 
static int kadane(List<int> v)
{
    int maxSoFar = 0;
    int maxEndingHere = 0;
 
    // Iterate array v
    for(int i = 0; i < v.Count; i++) 
    {
        maxEndingHere += v[i];
             
        // Update the maximum
        maxSoFar = Math.Max(maxEndingHere,
                            maxSoFar);
             
        // Update maxEndingHere to 0 if it
        // is less than 0
        maxEndingHere = Math.Max(maxEndingHere, 0);
    }
     
    // Return maximum sum
    return maxSoFar;
}
 
// Function to find the sum
// of even indexed elements
// after modification in array.
static int sumOfElements(int []arr, int n)
{
    int sum = 0;
 
    // Find initial sum of
    // even indexed elements
    for(int i = 0; i < n; i++)
    {
        if (i % 2 == 0)
            sum += arr[i];
    }
 
    // Create two vectors to store
    // the consecutive differences
    // of elements
    List<int> v1 = new List<int>();
    List<int> v2 = new List<int>();
 
    for(int i = 1; i < n; i += 2) 
    {
        v1.Add(arr[i] - arr[i - 1]);
         
        if (i + 1 < n)
        {
            v2.Add(arr[i] - arr[i + 1]);
        }
    }
     
    // Find the maximum sum subarray
    int option1 = kadane(v1);
    int option2 = kadane(v2);
 
    // Add the maximum value
    // to initial sum
    int ans = sum + Math.Max(option1,
                             option2);
 
    // Return the answer
    return ans;
}
 
// Driver Code
public static void Main(String[] args)
{
     
    // Given array []arr
    int []arr = { 5, 1, 3, 4, 5, 6 };
 
    int N = arr.Length;
 
    // Function call
    Console.Write(sumOfElements(arr, N));
}
}
 
// This code is contributed by Amit Katiyar

Javascript

<script>
// Javascript program for the above approach
 
// Kadane's Algorithm to find 
// the maximum sum sub array 
function kadane(v) 
{ 
    var maxSoFar = 0; 
    var maxEndingHere = 0; 
 
    // Iterate array v 
    for (var i = 0; i < v.length; i++) { 
 
        maxEndingHere += v[i]; 
 
        // Update the maximum 
        maxSoFar = Math.max(maxEndingHere,maxSoFar); 
 
        // Update maxEndingHere to 0 if it 
        // is less than 0 
        maxEndingHere = Math.max(maxEndingHere, 0); 
    } 
 
    // Return maximum sum 
    return maxSoFar; 
} 
 
// Function to find the sum 
// of even indexed elements 
// after modification in array. 
function sumOfElements(arr, n) 
{ 
    var sum = 0; 
 
    // Find initial sum of 
    // even indexed elements 
    for (var i = 0; i < n; i++) { 
        if (i % 2 == 0) 
            sum += arr[i]; 
    } 
 
    // Create two vectors to store 
    // the consecutive differences 
    // of elements 
    var v1 = []; 
    var v2 = []; 
 
    for (var i = 1; i < n; i += 2) { 
 
        v1.push(arr[i] - arr[i - 1]); 
 
        if (i + 1 < n) { 
            v2.push(arr[i] - arr[i + 1]); 
        } 
    } 
 
    // Find the maximum sum subarray 
    var option1 = kadane(v1); 
    var option2 = kadane(v2); 
 
    // Add the maximum value 
    // to initial sum 
    var ans = sum + Math.max(option1, 
                        option2); 
 
    // Return the answer 
    return ans; 
} 
 
 
var arr = [ 5, 1, 3, 4, 5, 6 ]; 
 
    var N = arr.length;
     
    // Function Call 
    document.write(sumOfElements(arr, N));
 
// This code is contributed by SoumikMondal
</script>

Output

Time Complexity: O(N), since traversal on the array is required to complete all operations hence the overall time required by the algorithm is linear.
Auxiliary Space: O(N), extra vectors are used hence algorithm takes up linear space.

AmanGupta65

Improve

Reverse a subarray to maximize sum of even-indexed elements of given array

Maximum sum of even indexed elements obtained by right shift on an even sized subarray

C++

Java

Python

C#

Javascript

C++

Java

Python3

C#

Javascript

Similar Reads

Please Login to comment...

What kind of Experience do you want to share?