building up the maximum sum decreasing subarray for each array index
msds [ n - 1 ] = arr [ n - 1 ] ; for ( int i = n - 2 ; i >= 0 ; i -- ) if ( arr [ i ] > arr [ i + 1 ] ) msds [ i ] = msds [ i + 1 ] + arr [ i ] ; else msds [ i ] = arr [ i ] ;