Apply the normal Kadane algorithm but on the elements of the array having inverted sign
$ sum_here = $ arr [ 0 ] ; $ max_sum = $ arr [ 0 ] ; for ( $ i = 1 ; $ i < $ n ; $ i ++ ) { $ sum_here = max ( $ sum_here + $ arr [ $ i ] , $ arr [ $ i ] ) ; $ max_sum = max ( $ max_sum , $ sum_here ) ; }