Apply the normal Kadane algorithm but on the elements of the array having inverted sign
sum_here = arr [ 0 ] NEW_LINE max_sum = arr [ 0 ] NEW_LINE for i in range ( 1 , n ) : NEW_LINE INDENT sum_here = max ( sum_here + arr [ i ] , arr [ i ] ) NEW_LINE max_sum = max ( max_sum , sum_here ) NEW_LINE DEDENT