Maximum Sum Alternating Subarray | C ++ implementation for the above approach ; Function to find the maximum alternating sum of a subarray for the given array ; Traverse the array ; Store sum of subarrays starting at even indices ; Update sum ; Traverse the array ; Store sum of subarrays starting at odd indices ; Update sum ; Driver code ; Given Input ; Function call
#include <bits/stdc++.h> NEW_LINE using namespace std ; int alternatingSum ( int arr [ ] , int n ) { int sum = 0 ; int sumSoFar = 0 ; for ( int i = 0 ; i < n ; i ++ ) { if ( i % 2 == 1 ) { sumSoFar -= arr [ i ] ; } else { sumSoFar = max ( sumSoFar + arr [ i ] , arr [ i ] ) ; } sum = max ( sum , sumSoFar ) ; } sumSoFar = 0 ; for ( int i = 1 ; i < n ; i ++ ) { if ( i % 2 == 0 ) { sumSoFar -= arr [ i ] ; } else { sumSoFar = max ( sumSoFar + arr [ i ] , arr [ i ] ) ; } sum = max ( sum , sumSoFar ) ; } return sum ; } int main ( ) { int arr [ ] = { -4 , -10 , 3 , 5 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; int ans = alternatingSum ( arr , n ) ; cout << ans << endl ; return 0 ; }