暑期刷题日记08

旧日不见，哥们又来水题解啦

最大子数组和

题目描述

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

子数组 是数组中的一个连续部分。

样例

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

算法

dp

维护一个以当前数字结尾的最大值和全局的最大值即可

状态转移方程： $curmax = max(curmax + nums[i], nums[i])$
由于题目要求子数组最少包含一个元素，所以是以nums[i]重新开始的

C++代码

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int maxn = nums[0], curmax = 0;
        for (auto num  : nums)
        {
            curmax = max(num, curmax + num);
            maxn = max(maxn, curmax);
        }

        return maxn;
    }
};

环形子数组的最大和

题目描述

给定一个长度为 n 的环形整数数组 nums ，返回 nums 的非空 子数组 的最大可能和 。

环形数组 意味着数组的末端将会与开头相连呈环状。形式上， nums[i] 的下一个元素是 nums[(i + 1) % n] ， nums[i] 的前一个元素是 nums[(i - 1 + n) % n] 。

子数组 最多只能包含固定缓冲区 nums 中的每个元素一次。形式上，对于子数组 nums[i], nums[i + 1], …, nums[j] ，不存在 i <= k1, k2 <= j 其中 k1 % n == k2 % n 。

样例

• 示例 1：

  输入：nums = [1,-2,3,-2]
  输出：3
  解释：从子数组 [3] 得到最大和 3 

• 示例 2：

  输入：nums = [5,-3,5]
  输出：10
  解释：从子数组 [5,5] 得到最大和 5 + 5 = 10

• 示例 3：

  输入：nums = [3,-2,2,-3]
  输出：3
  解释：从子数组 [3] 和 [3,-2,2] 都可以得到最大和 3

算法

dp，但不是区间dp

由于数据范围比较大，所以不能用区间dp，但是由于子数组要求要连续，那么就出现了如图的两种情况

第一种情况是子数组首尾不相连。
第二种是子数组一部分在头部一部分在尾部
所以最大的环形子数组和 = max(最大子数组和，数组总和-最小子数组和)

所以需要统计以当前数字结尾的最大子数组和与最小值子数组和，来动态更新最大子数组和与最小子数组和。
同样由于题目要求子数组不能为空，所以转移方程为:

• $curmax = max(nums[i], curmax + nums[i]);$
• $curmin = min(nums[i], curmin + nums[i]);$

C++代码

class Solution {
public:
    int maxSubarraySumCircular(vector<int>& nums) {
        int n = nums.size();

        int total = 0;
        int maxn = nums[0], minn = nums[0];
        int curmax = 0, curmin = 0;
        for (int i = 0; i < n; i ++)
        {
            curmax = max(nums[i], curmax + nums[i]);
            curmin = min(nums[i], curmin + nums[i]);
            maxn = max(maxn, curmax);
            minn = min(minn, curmin);
            total += nums[i];
        }
        return maxn < 0 ? maxn : max(maxn, total - minn);
    }
};