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){
for ( int j=i; j<n; j+=2){
for ( int k=i; k<=j; k+=2){
swap(arr[k], arr[k+1]);
}
int sum = 0;
for ( int x=0; x<n; x+=2){
sum += arr[x];
}
max_sum = max(max_sum, sum);
for ( int k=i; k<=j; k+=2){
swap(arr[k], arr[k+1]);
}
}
}
cout<<max_sum<<endl;
return 0;
}
|
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 ;
for ( int i = 0 ; i < n; i += 2 ) {
for ( int j = i; j < n; j += 2 ) {
for ( int k = i; k <= j; k += 2 ) {
int temp = arr[k];
arr[k] = arr[k + 1 ];
arr[k + 1 ] = temp;
}
int sum = 0 ;
for ( int x = 0 ; x < n; x += 2 ) {
sum += arr[x];
}
max_sum = Math.max(max_sum, sum);
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);
}
}
|
Python
def main():
arr = [ 5 , 1 , 3 , 4 , 5 , 6 ]
n = len (arr)
max_sum = 0
for i in range ( 0 , n, 2 ):
for j in range (i, n, 2 ):
for k in range (i, j + 1 , 2 ):
arr[k], arr[k + 1 ] = arr[k + 1 ], arr[k]
sum_even = sum (arr[ 0 :: 2 ])
max_sum = max (max_sum, sum_even)
for k in range (i, j + 1 , 2 ):
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;
for ( int i = 0; i < n; i += 2) {
for ( int j = i; j < n; j += 2) {
for ( int k = i; k <= j; k += 2) {
int temp = arr[k];
arr[k] = arr[k + 1];
arr[k + 1] = temp;
}
int sum = 0;
for ( int x = 0; x < n; x += 2) {
sum += arr[x];
}
max_sum = Math.Max(max_sum, sum);
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);
}
}
|
Javascript
function maxEvenSum(arr) {
const n = arr.length;
let max_sum = 0;
for (let i = 0; i < n; i += 2) {
for (let j = i; j < n; j += 2) {
for (let k = i; k <= j; k += 2) {
[arr[k], arr[k + 1]] = [arr[k + 1], arr[k]];
}
let sum = 0;
for (let x = 0; x < n; x += 2) {
sum += arr[x];
}
max_sum = Math.max(max_sum, sum);
for (let k = i; k <= j; k += 2) {
[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);
|
Time Complexity: O(N2)
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++
#include <bits/stdc++.h>
using namespace std;
int kadane(vector< int > v)
{
int maxSoFar = 0;
int maxEndingHere = 0;
for ( int i = 0; i < v.size(); i++) {
maxEndingHere += v[i];
maxSoFar = max(maxEndingHere,
maxSoFar);
maxEndingHere
= max(maxEndingHere, 0);
}
return maxSoFar;
}
int sumOfElements( int * arr, int n)
{
int sum = 0;
for ( int i = 0; i < n; i++) {
if (i % 2 == 0)
sum += arr[i];
}
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]);
}
}
int option1 = kadane(v1);
int option2 = kadane(v2);
int ans = sum + max(option1,
option2);
return ans;
}
int main()
{
int arr[] = { 5, 1, 3, 4, 5, 6 };
int N = sizeof (arr) / sizeof (arr[0]);
cout << sumOfElements(arr, N);
return 0;
}
|
Java
import java.util.*;
class GFG{
static int kadane(Vector<Integer> v)
{
int maxSoFar = 0 ;
int maxEndingHere = 0 ;
for ( int i = 0 ; i < v.size(); i++)
{
maxEndingHere += v.get(i);
maxSoFar = Math.max(maxEndingHere,
maxSoFar);
maxEndingHere = Math.max(maxEndingHere, 0 );
}
return maxSoFar;
}
static int sumOfElements( int []arr, int n)
{
int sum = 0 ;
for ( int i = 0 ; i < n; i++)
{
if (i % 2 == 0 )
sum += arr[i];
}
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 ]);
}
}
int option1 = kadane(v1);
int option2 = kadane(v2);
int ans = sum + Math.max(option1,
option2);
return ans;
}
public static void main(String[] args)
{
int arr[] = { 5 , 1 , 3 , 4 , 5 , 6 };
int N = arr.length;
System.out.print(sumOfElements(arr, N));
}
}
|
Python3
def kadane(v):
maxSoFar = 0 ;
maxEndingHere = 0 ;
for i in range ( len (v)):
maxEndingHere + = v[i];
maxSoFar = max (maxEndingHere,
maxSoFar);
maxEndingHere = max (maxEndingHere, 0 );
return maxSoFar;
def sumOfElements(arr, n):
sum = 0 ;
for i in range (n):
if (i % 2 = = 0 ):
sum + = arr[i];
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 ]);
option1 = kadane(v1);
option2 = kadane(v2);
ans = sum + max (option1, option2);
return ans;
if __name__ = = "__main__" :
arr = [ 5 , 1 , 3 , 4 , 5 , 6 ];
N = len (arr);
print (sumOfElements(arr, N));
|
C#
using System;
using System.Collections.Generic;
class GFG{
static int kadane(List< int > v)
{
int maxSoFar = 0;
int maxEndingHere = 0;
for ( int i = 0; i < v.Count; i++)
{
maxEndingHere += v[i];
maxSoFar = Math.Max(maxEndingHere,
maxSoFar);
maxEndingHere = Math.Max(maxEndingHere, 0);
}
return maxSoFar;
}
static int sumOfElements( int []arr, int n)
{
int sum = 0;
for ( int i = 0; i < n; i++)
{
if (i % 2 == 0)
sum += arr[i];
}
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]);
}
}
int option1 = kadane(v1);
int option2 = kadane(v2);
int ans = sum + Math.Max(option1,
option2);
return ans;
}
public static void Main(String[] args)
{
int []arr = { 5, 1, 3, 4, 5, 6 };
int N = arr.Length;
Console.Write(sumOfElements(arr, N));
}
}
|
Javascript
<script>
function kadane(v)
{
var maxSoFar = 0;
var maxEndingHere = 0;
for ( var i = 0; i < v.length; i++) {
maxEndingHere += v[i];
maxSoFar = Math.max(maxEndingHere,maxSoFar);
maxEndingHere = Math.max(maxEndingHere, 0);
}
return maxSoFar;
}
function sumOfElements(arr, n)
{
var sum = 0;
for ( var i = 0; i < n; i++) {
if (i % 2 == 0)
sum += arr[i];
}
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]);
}
}
var option1 = kadane(v1);
var option2 = kadane(v2);
var ans = sum + Math.max(option1,
option2);
return ans;
}
var arr = [ 5, 1, 3, 4, 5, 6 ];
var N = arr.length;
document.write(sumOfElements(arr, N));
</script>
|
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.