Minimum Subarray

Question

Given an array of integers, find the subarray with smallest sum.

Return the sum of the subarray.

Example For [1, -1, -2, 1], return -3

Note The subarray should contain at least one integer.

Thoughts

和maximum subarray一样，用dynamic programming做，if condition不一样

Solution

class Solution:
    """
    @param nums: a list of integers
    @return: A integer denote the sum of minimum subarray
    """
    def minSubArray(self, nums):
        # write your code here
        if not nums:
            return 0
        currentSum = 0
        length = len(nums)
        minSum = sys.maxint
        for i in range(length):
            if currentSum > 0:
                currentSum = nums[i]
            else:
                currentSum += nums[i]
            if minSum > currentSum:
                minSum = currentSum
        return minSum