Smallest sum contiguous subarray | Set | function to find the smallest sum contiguous subarray ; First invert the sign of the elements ; Apply the normal Kadane algorithm but on the elements of the array having inverted sign ; Invert the answer to get minimum val ; Driver Code
def smallestSumSubarr ( arr , n ) : NEW_LINE INDENT for i in range ( n ) : NEW_LINE INDENT arr [ i ] = - arr [ i ] NEW_LINE DEDENT 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 return ( - 1 ) * max_sum NEW_LINE DEDENT arr = [ 3 , - 4 , 2 , - 3 , - 1 , 7 , - 5 ] NEW_LINE n = len ( arr ) NEW_LINE print ( " Smallest ▁ sum : " , smallestSumSubarr ( arr , n ) ) NEW_LINE