0053._maximum_subarray.md

Links:

1. https://leetcode.com/problems/maximum-subarray/
2. https://leetcode-cn.com/problems/maximum-subarray/

Tags

1. 数组
2. 分治算法
3. 动态规划

思想

如果数字 > 0，则说明对结果有增益。 如果数字 <= 0，则说明对结果没有增益。可以舍弃。

Solution 1 暴力法

class Solution(object):
    def maxSubArray(self, nums):
        max_num = nums[0]
        cur_sum = 0
        for num in nums:
            cur_sum = cur_sum + num
            if cur_sum > max_num:
                max_num = cur_sum
            if  cur_sum < 0:
                cur_sum = 0
        return max_num

---

class Solution:
    def maxSubArray(self, nums):
        cur_sum = max_sum = nums[0]
        for num in nums[1:]:
            cur_sum = max(num, cur_sum + num)
            max_sum = max(max_sum, cur_sum)

        return max_sum

---

Go

func maxSubArray(nums []int) int {
    max := nums[0]
    cur := 0

    for _, v := range nums {
        cur += v
        
        if cur > max{
            max = cur
        }
        
        if cur < 0 {
            cur = 0
        }
    }

    return max
}

Solution 2 动态规划

dp: 分治 + memo。只关注：当然值 和 当前值+过去的状态。（只关注当前的子问题和过去的子问题）

1. dp问题. 公式为: dp[i] = max(nums[i], nums[i] + dp[i - 1])
2. 最大子序和 = 当前元素自身最大, 或者 包含之前后最大

class Solution(object):
    def maxSubArray(self, nums):
        for i in range(1, len(nums)):
            # nums[i - 1]代表dp[i - 1]
            nums[i] = max(nums[i], nums[i] + nums[i - 1])

        return max(nums)

---

class Solution(object):
    def maxSubArray(self, nums):
        dp = []
        dp.append(nums[0])
        for i in range(1, len(nums)):
                dp.append(max(nums[i], nums[i] + dp[-1]))
        return max(dp)

---

class Solution(object):
    def maxSubArray(self, nums):
        dp = []
        dp.append(nums[0])
        for i in range(1, len(nums)):
            if dp[-1] > 0:
                dp.append(nums[i] + dp[-1])
            else:
                dp.append(nums[i])
        return max(dp)

---

class Solution(object):
    def maxSubArray(self, nums):
        dp = [0]*len(nums)
        dp[0] = nums[0]
        
        for i in range(1, len(nums)):
            dp[i] = max(nums[i], dp[i - 1]+nums[i])
        
        return max(dp)

---

Go

func max(a int, b int) int {
	if a > b {
		return a
	}
	return b
}

func maxSubArray(nums []int) int {
    dp, result := make([]int, len(nums)), nums[0]
    dp[0] = nums[0]

    for i := 1; i < len(nums); i++ {
        dp[i] = max(nums[i], dp[i-1]+nums[i])
        result = max(dp[i], result)
    }

    return result
}