PeterQwQ
0%

Leetcode 53 最大子数组和

发表于 更新于

给你一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。 子数组是数组中的一段连续部分。

拿到这个一开始的思路是前缀和，只需要遍历一遍数组，算出当前的前缀和，然后找到之前的最小前缀和，然后用当前的前缀和减去最小前缀和，就是当前的最大和。

同时注意，我们这里的前缀和是从0开始的，所以我们要把前缀和的最小值设为0，这样才能保证我们的最大和是正确的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        if len(nums)==1:
            return nums[0]
        ans = -inf
        prefix = [0]*(len(nums)+1)
        for i in range(len(nums)):
            if i != 0:
                prefix_now = nums[i] + prefix[i-1]
            else:
                prefix_now = nums[i]
            prefix_min = min(prefix[:i+1])
            prefix[i] = prefix_now
            ans = max(prefix_now - prefix_min, ans)
        return ans

但是这个写法TLE了，感觉是 min 和 max 遍历了整个数组导致的。所以只需要用一个变量来记录而不是数组来记录，应该就不会TLE了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        if len(nums)==1:
            return nums[0]
        ans = -inf
        prefix_min = 0
        prefix = 0
        for i in range(len(nums)):
            if i != 0:
                prefix = nums[i] + prefix
            else:
                prefix = nums[i]
            ans = max(prefix - prefix_min, ans)
            prefix_min = min(prefix, prefix_min)
        return ans

看题解还可以动态规划写，具体的思路就是对于我们需要得到的最大数组和 f[i] ，无非就是两种途径：f[i] = f[i-1] + nums[i] 或者 f[i] = nums[i] 。很好理解，如果加上前一个数的和比当前数还小，那么就不如直接从当前数开始。所以我们可以写出动态规划的代码：
1
2
3
4
5
6
7
8
9
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        '''
        f[i] = max(f[i-1] + nums[i], nums[i])
        '''
        f = [0]*len(nums)
        for i in range(len(nums)):
            f[i] = max(f[i-1]+nums[i], nums[i])
        return max(f)