力扣数组基础题（4）最大子数组和

题目

https://leetcode.com/problems/maximum-subarray/

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

自解

暴力解

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
def maxSubArray(self, nums: List[int]) -> int:
    maxsum=nums[0]
    for i in range(len(nums)):
        if len(nums)==1:
            maxsum=nums[0]
            break
        sum=nums[i]
        for j in range(i+1,len(nums)):
            sum=sum+nums[j]                
            maxsum=max(maxsum,sum)
    return maxsum    

练了一题后，每道题只能先想到暴力解

[!hint] 假设你在玩一个赚钱游戏，数组里的数字是每一天的盈亏。你的目标是找到一段连续的日子，让总收益最大。
如果之前的总收益是正数，那么加上今天的盈亏，对以后肯定是有好处的。
如果之前的总收益已经变成了负数（欠债了！），那么对于明天来说，带上之前的负债只会让你赚得更少。

在 G 老师的提示下写出下面的解，感觉不是很严谨

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
def maxSubArray(self, nums: List[int]) -> int:
    sum=0
    maxsum=nums[0]
    for i in range(len(nums)):
        if len(nums)==1:
            sum=nums[0]
            break
        if sum >=0:
            sum=sum+nums[i]
        if sum < 0:
            sum=0
        maxsum=max(sum,maxsum)
    return maxsum    

题解

前缀和 + 贪心

首先我们需要知道什么是前缀和？前缀和可以简单理解为「一个数组前 𝑛 项的和」。下面是一个例子。

有数组 nums=[1,2,3,4]，要想计算子数组 [3,4] 的元素和，可以用前缀和 [1,2,3,4] ，减去另一个前缀和 [1,2] 。

由此，任意子数组的和，都可以表示为两个前缀和的差。我们对数组进行 $O(n)$ 预处理，能够将单次查询区间和的复杂度降低到 $O(1)$ 。

求出 nums 的前缀和，就可以用前缀和来表示区间和，问题就变成求最大的区间和，这和买卖股票的最佳时机的思想相似。

1
2
3
4
5
6
7
8
def maxSubArray(self, nums: List[int]) -> int:
    presum=presum_min=0
    maxsub=-inf
    for num in nums:
        presum+=num
        maxsub=max(maxsub,presum-presum_min)
        presum_min=min(presum,presum_min)
    return maxsub  

写得迷迷糊糊，最后没有对 ans 取最大值。先计算 maxsub 还是最小前缀和可以用特例来确定。如输入数组为[-1]，先更新最小前缀和会导致最后序列和为 0。

参考

https://leetcode.cn/problems/maximum-subarray/solutions/2533977/qian-zhui-he-zuo-fa-ben-zhi-shi-mai-mai-abu71/ https://oi-wiki.org/basic/prefix-sum/