Modify array to maximize sum of adjacent differences | 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
< ? php function maximumDifferenceSum ( $ arr , $ N ) { $ dp = array ( array ( ) ) ; for ( $ i = 0 ; $ i < $ N ; $ i ++ ) $ dp [ $ i ] [ 0 ] = $ dp [ $ i ] [ 1 ] = 0 ; for ( $ 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 ] ) ; } $ arr = array ( 3 , 2 , 1 , 4 , 5 ) ; $ N = count ( $ arr ) ; echo maximumDifferenceSum ( $ arr , $ N ) ; ? >