text: Compute maximum of the function efficiently over all sub | Java implementation of the 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: import java . util . * ; class GFG { static int MAX = 100005 ; static int kadaneAlgorithm ( 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 = Math . max ( maxSum , sum ) ; } return maxSum ; } static int maxFunction ( int [ ] arr , int n ) { int [ ] b = new int [ MAX ] ; int [ ] c = new int [ MAX ] ; for ( int i = 0 ; i < n - 1 ; i ++ ) { if ( i % 2 == 1 ) { b [ i ] = Math . abs ( arr [ i + 1 ] - arr [ i ] ) ; c [ i ] = - b [ i ] ; } else { c [ i ] = Math . abs ( arr [ i + 1 ] - arr [ i ] ) ; b [ i ] = - c [ i ] ; } } int ans = kadaneAlgorithm ( b , n - 1 ) ; ans = Math . max ( ans , kadaneAlgorithm ( c , n - 1 ) ) ; return ans ; } public static void main ( String [ ] args ) { int arr [ ] = { 1 , 5 , 4 , 7 } ; int n = arr . length ; System . out . println ( maxFunction ( arr , n ) ) ; } }