53. Maximum Subarray

求一个数组中和最大的子数组。

思路：动态规划，如果当前的子数组的和大于0，则继续加上当前的数值，如果小于0，则等于当前的数值，然后每次与当前的最大和比较

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        # 6 star, 思路很巧妙，必须掌握
        current_sum, max_sum = -0xffffffff, -0xffffffff
        for i in nums:
            if current_sum < 0:
                current_sum = i
            else:
                current_sum += i
            if current_sum > max_sum:
                max_sum = current_sum
        return max_sum

Go:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 这个解法更清晰一些，curSum = max(nums[i], curSum + nums[i]), maxSum = max(curSum, maxSum)
func maxSubArray(nums []int) int {
	curSum, maxSum := nums[0], nums[0]
	for _, val := range nums[1:] {
		if curSum + val > val {
			curSum += val
		} else {
			curSum = val
		}
		if curSum > maxSum {maxSum = curSum}
	}
	return maxSum

}