Modify array to maximize sum of adjacent differences | C ++ program to get maximum consecutive element difference sum ; Returns maximum - difference - sum with array modifications allowed . ; Initialize dp [ ] [ ] with 0 values . ; for [ i + 1 ] [ 0 ] ( i . e . current modified value is 1 ) , choose maximum from dp [ i ] [ 0 ] + abs ( 1 - 1 ) = dp [ i ] [ 0 ] and dp [ i ] [ 1 ] + abs ( 1 - arr [ i ] ) ; for [ i + 1 ] [ 1 ] ( i . e . current modified value is arr [ i + 1 ] ) , choose maximum from dp [ i ] [ 0 ] + abs ( arr [ i + 1 ] - 1 ) and dp [ i ] [ 1 ] + abs ( arr [ i + 1 ] - arr [ i ] ) ; Driver code to test above methods
#include <bits/stdc++.h> NEW_LINE using namespace std ; int maximumDifferenceSum ( int arr [ ] , int N ) { int dp [ N ] [ 2 ] ; for ( int i = 0 ; i < N ; i ++ ) dp [ i ] [ 0 ] = dp [ i ] [ 1 ] = 0 ; for ( int i = 0 ; i < ( N - 1 ) ; i ++ ) { dp [ i + 1 ] [ 0 ] = max ( dp [ i ] [ 0 ] , dp [ i ] [ 1 ] + abs ( 1 - arr [ i ] ) ) ; dp [ i + 1 ] [ 1 ] = max ( dp [ i ] [ 0 ] + abs ( arr [ i + 1 ] - 1 ) , dp [ i ] [ 1 ] + abs ( arr [ i + 1 ] - arr [ i ] ) ) ; } return max ( dp [ N - 1 ] [ 0 ] , dp [ N - 1 ] [ 1 ] ) ; } int main ( ) { int arr [ ] = { 3 , 2 , 1 , 4 , 5 } ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; cout << maximumDifferenceSum ( arr , N ) << endl ; return 0 ; }