最大子数组和

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

示例 1：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4] 输出：6 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。 示例 2：

输入：nums = [1] 输出：1 示例 3：

输入：nums = [5,4,-1,7,8] 输出：23

这题思路有很多，先讲贪心。用一个数来记录累积和，当和小于0时，就将和置为0，因为负数加上任何数都会变小。然后用一个数来记录最大和，每次更新最大和。

class Solution {
public:
  int maxSubArray(vector<int>& nums) {
    int res=0;
    int maxsum=INT_MIN;
    for(auto n:nums){
      res+=n;
      if(res > maxsum) maxsum=res;
      if(res<=0) res=0;
    }
    return maxsum;
  }
};

其次还有个灵神前缀和的思路，前缀和之前没咋用过，现在要尝试着用了。 定义前缀和如下

$$s [ 0 ]=0 \;, \; \; s [ i+1 ]=\sum_{j=0}^{i} n u m s [ j ] \;.$$

那么对于子数组 $nums[left..right]$，它的和就可以表示为：

$$\sum_{j=l e f t}^{r i g h t} n u m s [ j ]=\sum_{j=0}^{r i g h t} n u m s [ j ]-\sum_{j=0}^{l e f t-1} n u m s [ j ]=s [ r i g h t+1 ]-s [ l e f t ]$$

注：$s[0]=0$ 表示一个空数组的元素和。为什么要额外定义它？想一想，如果要计算的子数组恰好是一个前缀（从 nums[0] 开始），你要用 $s[right]$ 减去谁呢？通过定义 $s[0]=0$，任意子数组（包括前缀）都可以表示为两个前缀和的差。 由于子数组的元素和等于两个前缀和的差，所以求出 nums 的前缀和，问题就变成买卖股票的最佳时机。本题子数组不能为空，相当于一定要交易一次。

我们可以一边遍历数组计算前缀和，一边维护前缀和的最小值（相当于股票最低价格），用当前的前缀和（卖出价格）减去前缀和的最小值（买入价格），就得到了以当前元素结尾的子数组和的最大值（利润），用它来更新答案的最大值（最大利润）。

class Solution {
public:
  int maxSubArray(vector<int>& nums) {
    int ans = INT_MIN;
    int min_pre_sum = 0;
    int pre_sum = 0;
    for (int x : nums) {
      pre_sum += x; 
      // 当前的前缀和
      ans = max(ans, pre_sum - min_pre_sum); 
      // 减去前缀和的最小值
      min_pre_sum = min(min_pre_sum, pre_sum); 
      // 维护前缀和的最小值
    }
    return ans;
  }
};

更新日志

2024/12/13 13:22

查看所有更新日志

• 24fac-prepare interview于 2024/12/13