text: Compute maximum of the function efficiently over all sub | C ++ implementation of the above approach ; Function to return maximum sum of a sub - array ; Function to return maximum value of function F ; Compute arrays B [ ] and C [ ] ; Find maximum sum sub - array of both of the arrays and take maximum among them ; Driver code
code: #include <bits/stdc++.h> NEW_LINE #define MAX  100005 NEW_LINE using namespace std ; int kadaneAlgorithm ( const int * ar , int n ) { int sum = 0 , maxSum = 0 ; for ( int i = 0 ; i < n ; i ++ ) { sum += ar [ i ] ; if ( sum < 0 ) sum = 0 ; maxSum = max ( maxSum , sum ) ; } return maxSum ; } int maxFunction ( const int * arr , int n ) { int b [ MAX ] , c [ MAX ] ; for ( int i = 0 ; i < n - 1 ; i ++ ) { if ( i & 1 ) { b [ i ] = abs ( arr [ i + 1 ] - arr [ i ] ) ; c [ i ] = - b [ i ] ; } else { c [ i ] = abs ( arr [ i + 1 ] - arr [ i ] ) ; b [ i ] = - c [ i ] ; } } int ans = kadaneAlgorithm ( b , n - 1 ) ; ans = max ( ans , kadaneAlgorithm ( c , n - 1 ) ) ; return ans ; } int main ( ) { int arr [ ] = { 1 , 5 , 4 , 7 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; cout << maxFunction ( arr , n ) ; return 0 ; }