Minimum Subarray

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.

Solution

典型的贪心算法问题，思路是从数组第一个数字开始进行累加，用一个int统计最小的和(minimum sum of sub array) - 初始值为INT_MAX，用一个int统计当前的和 - 初始值为0。

int minSum = INT_MAX;

int currentSum = 0;

然后开始遍历数组，对当前遍历到的数组元素进行累加，如果累加器currentSum得到的值小于minSum，则记录currentSum为minSum。

然后判断currentSum是否为>0，如果大于0，则可以认为，从此处往前的数字都可以抹掉（为什么-贪心策略），并将currentSum重置为0，重新计数。

通过对数组循环的遍历，最后得到的minSum即为题目所求的minSubArray。

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
        total, sum = sys.maxint, 0

        for num in nums:
            sum += num
            total = min(total, sum)
            sum = min(sum, 0)

        return total