前两天在忙着搞大数据和论文，论文写差不多了，开始刷刷题，前几天笔试做的一塌糊涂，有的题明明感觉做对了，但是AC不了。趁着最近有空，赶紧找找感觉。
一道简单的贪心题

44.最小子数组

给定一个整数数组，找到一个具有最小和的子数组。返回其最小和。

样例

给出数组[1, -1, -2, 1]，返回 -3

注意事项

子数组最少包含一个数字

解：

从第一个数往后遍历i=1->n
将前k个数视为一个整体，如果这个整体>0,则后面无论是什么，只要加上这个整体，肯定不会变小，所以整体直接舍弃，剩下的为新的数组nums.
如果，前面的数为负，如前3个数的和为-7，第4个数为8，则-7+8=1,要不要舍弃呢？后面可能没有小于-7的子数组了呀？所以 我们还要有个变量res，用来保存各阶段的最小值，如这里的-7，如果后面有比-7更小的子数组，就更新这个变量的值，如果没有，res就是一直是-7。
python3代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution:
    """
    @param: nums: a list of integers
    @return: A integer indicate the sum of minimum subarray
    """
    def minSubArray(self, nums):
        # write your code here

        sum = 0
        res = nums[0]
        for i in nums:
            sum+=i
            if sum < res:
                res = sum
            if sum > 0:
                sum = 0
        return res

刚开始不通过,看了下数据[1,1],全是正数，而我当时设的res初值为0.本来以为至少会有1个负值。
所以把初值改为了第一个数。

每天一点 进步不难