Smallest sum contiguous subarray | Python program to find the smallest sum contiguous subarray ; function to find the smallest sum contiguous subarray ; to store the minimum value that is ending up to the current index ; to store the minimum value encountered so far ; traverse the array elements ; if min_ending_here > 0 , then it could not possibly contribute to the minimum sum further ; else add the value arr [ i ] to min_ending_here ; update min_so_far ; required smallest sum contiguous subarray value ; Driver code
import sys NEW_LINE def smallestSumSubarr ( arr , n ) : NEW_LINE INDENT min_ending_here = sys . maxsize NEW_LINE min_so_far = sys . maxsize NEW_LINE for i in range ( n ) : NEW_LINE INDENT if ( min_ending_here > 0 ) : NEW_LINE INDENT min_ending_here = arr [ i ] NEW_LINE DEDENT else : NEW_LINE INDENT min_ending_here += arr [ i ] NEW_LINE DEDENT min_so_far = min ( min_so_far , min_ending_here ) NEW_LINE DEDENT return min_so_far 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