顾得泉：个人主页
个人专栏：《Linux操作系统》 《C/C++》 《LeedCode刷题》
键盘敲烂，年薪百万！
一、最大子数组和
题目链接：最大子数组和
题目描述
给你一个整数数组 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
提示：
1 <= nums.length <= 105-104 <= nums[i] <= 104
解法
1.状态表示:
对于线性dp，我们可以用「经验＋题目要求」来定义状态表示:
i.以某个位置为结尾，巴拉巴拉;
ii.以某个位置为起点，巴拉巴拉。
这里我们选择比较常用的方式，以「某个位置为结尾」
结合「题目要求」，定义一个状态表示:
dp[i]表示:以i位置元素为结尾的「所有子数组」中和的最大和
2.状态转移方程:
dp[i]的所有可能可以分为以下两种
i.子数组的长度为1:此时dpLi= nums[i];
ii.子数组的长度大于1:此时 dp[i]应该等于以i - 1做结尾的「所有子数组」中和的最大值再加上nums[i]，也就是dp[i - 1]+ nums[i]
由于我们要的是最大值,因此应该是两种情况下的最大值，因此可得转移方程:
dp[i] = max (nums[i]，dp[i - 1]+ nums[i])
3.初始化:
可以在最前面加上一个「辅助结点」，帮助我们初始化。使用这种技巧要注意两个点:
i.辅助结点里面的值要「保证后续填表是正确的」;
ii.「下标的映射关系」
在本题中，最前面加上一个格子，并且让dp[0] = 即可
4.填表顺序:
根据「状态转移方程」易得，填表顺序为「从左往右」
5.返回值:
状态表示为「以1为结尾的所有子数组」的最大值，但是最大子数组和的结尾我们是不确定的。因此我们需要返回整个dp表中的最大值
代码实现
class Solution {
public:int maxSubArray(vector<int>& nums) {int n = nums.size();vector<int> dp(n + 1);int ret = INT_MIN;for(int i = 1; i <= n; i++){dp[i] = max(nums[i - 1], dp[i - 1] + nums[i - 1]);ret = max(ret, dp[i]);}return ret;}
};二、环形子数组的最大和
题目链接：环形子数组的最大和
题目描述
给定一个长度为 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
提示：
n == nums.length1 <= n <= 3 * 104-3 * 104 <= nums[i] <= 3 * 104
解法
本题与「最大子数组和」的区别在于，考虑问题的时候不仅要分析「数组内的连续区域」，还要考虑「数组首尾相连」的一部分。结果的可能情况分为以下两种:
i.结果在数组的内部，包括整个数组;
ii.结果在数组首尾相连的一部分上
其中，对于第一种情况，我们仅需按照「最大子数组和」的求法就可以得到结果，记为 fmax。对于第二种情况，我们可以分析一下:
i.如果数组首尾相连的一部分是最大的数组和，那么数组中间就会空出来一部分;
ii.因为数组的总和sum是不变的，那么中间连续的一部分的和一定是最小的;因此，我们就可以得出一个结论，对于第二种情况的最大和，应该等于sum - gmin
其中,gmin表示数组内的「最小子数组和」
两种情况下的最大值，就是我们要的结果
但是，由于数组内有可能全部都是负数，第一种情况下的结果是数组内的最大值(是个负数)，第二种情况下的 gmin == sum，求的得结果就会是0。若直接求两者的最大值，就会是0。但是实际的结果应该是数组内的最大值。对于这种情况，我们需要特殊判断一下
由于「最大子数组和」的方法已经讲过，这里只提一下「最小子数组和」的求解过程，其实与「最大子数组和」的求法是一致的。用f表示最大和，g表示最小和
1.状态表示:
g[i]表示:以i做结尾的所有子数组中和的最小值
2.状态转移方程:
g[i]的所有可能可以分为以下两种:
i.子数组的长度为1 :此时g[i] = nums[i] ;
ii.子数组的长度大于1∶此时 g[i应该等于以i - 1做结尾的「所有子数组」中和的最小值再加上nums[i]，也就是g[i - 1] + nums[i]
由于我们要的是最小子数组和，因此应该是两种情况下的最小值，因此可得转移方程:
g[i] = min( nums[i]，g[i - 1]+ nums[i])
3.初始化:
可以在最前面加上一个辅助结点，帮助我们初始化。使用这种技巧要注意两个点:
i.辅助结点里面的值要保证后续填表是正确的;
ii.下标的映射关系
在本题中，最前面加上一个格子，并且让g[0]= 0即可
4.填表顺序:
根据状态转移方程易得，填表顺序为「从左往右」
5.返回值:
a.先找到f表里面的最大值->fmax ;
b.找到g表里面的最小值-> gmin ;
c.统计所有元素的和->sum ;
d.返回sum == gmin ? fmax : max ( fmax, sum - gmin)
代码实现
class Solution {
public:int maxSubarraySumCircular(vector<int>& nums) {int n = nums.size();vector<int> f(n + 1), g(n + 1);int fmax = INT_MIN, gmin = INT_MAX, sum = 0;for(int i = 1; i <= n; i++){int x = nums[i - 1];f[i] = max(x, x + f[i - 1]);fmax = max(fmax, f[i]);g[i] = min(x, x + g[i - 1]);gmin = min(gmin, g[i]);sum += x;}return sum == gmin ? fmax : max(fmax, sum - gmin);}
};三、乘积最大子数组
题目链接：乘积最大子数组
题目描述
给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积
测试用例的答案是一个 32-位 整数
子数组 是数组的连续子序列
示例 1:
输入: nums = [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6
示例 2:
输入: nums = [-2,0,-1] 输出: 0 解释: 结果不能为 2, 因为 [-2,-1] 不是子数组
提示:
1 <= nums.length <= 2 * 104-10 <= nums[i] <= 10nums的任何前缀或后缀的乘积都 保证 是一个 32-位 整数
解法
这道题与「最大子数组和」非常相似，我们可以效仿着定义一下状态表示以及状态转移:
i. dp[i]表示以i为结尾的所有子数组的最大乘积，
ii. dp[i] = max ( nums[i]，dp[i - 1]* nums[i]);
由于正负号的存在，我们很容易就可以得到，这样求dp[i的值是不正确的。因为 dp[i -1]的信息并不能让我们得到dp[i]的正确值。比如数组[-2，5，-2]，用上述状态转移得到的dp数组为[-2，5，-2]，最大乘积为5。但是实际上的最大乘积应该是所有数相乘，结果为20
究其原因，就是因为我们在求dp[2]的时候，因为nums[2]是一个负数，因此我们需要的是「 i - 1位置结尾的最小的乘积(-10)」，这样一个负数乘以「最小值」，才会得到真实的最大值。因此，我们不仅需要一个「乘积最大值的dp表」，还需要一个「乘积最小值的dp表」
1．状态表示:
f[i]表示:以i结尾的所有子数组的最大乘积
g[i]表示:以i结尾的所有子数组的最小乘积
2．状态转移方程:
遍历每一个位置的时候，我们要同步更新两个dp数组的值。
对于f[i]，也就是「以为结尾的所有子数组的最大乘积」，对于所有子数组，可以分为下面三种形式:
i.子数组的长度为1，也就是nums[i] ;
ii.子数组的长度大于1，但nums[i] > 0，此时需要的是i - 1为结尾的所有子数组的最大乘积f[i - 1]，再乘上nums[i]，也就是nums[i] * f[i - 1];
ili.子数组的长度大于1，但nums[i]<0，此时需要的是i - 1为结尾的所有子数组的最小乘积g[i - 1]，再乘上nums[i]，也就是nums[i] * g[i - 1];(如果nums[i] = 0，所有子数组的乘积均为0，三种情况其实都包含了)
综上所述，f[i] = max(nums[i]，max(nums[i] * f[i - 1]，nums[i] * g[i -1]))。
对于g[i]，也就是「以1为结尾的所有子数组的最小乘积」，对于所有子数组，可以分为下面三种形式:
i.子数组的长度为1，也就是nums[i];
ii.子数组的长度大于1)，但nums[i] > 0，此时需要的是i – 1为结尾的所有子数组的最小乘积g[i - 1]，再乘上nums[i]，也就是nums[i] * g[i - 1];
iii.子数组的长度大于1，但nums[i] < 0，此时需要的是i - 1为结尾的所有子数组的最大乘积f[i - 1]，再乘上nums[i]，也就是nums[i] * f[i - 1];
综上所述，g[i] = min(nums[i]，min(nums[i] * f[i - 1]，nums[i] * g[i -1]))
(如果nums[i] = 0，所有子数组的乘积均为0，三种情况其实都包含了）
3.初始化:
可以在最前面加上一个辅助结点，帮助我们初始化。使用这种技巧要注意两个点:
i.辅助结点里面的值要保证后续填表是正确的;
ii.下标的映射关系。
在本题中，最前面加上一个格子，并且让f[o]=g[o]=1即可
4.填表顺序:
根据状态转移方程易得，填表顺序为从左往右，两个表一起填
5.返回值:
返回f表中的最大值
代码实现
class Solution {
public:int maxProduct(vector<int>& nums) {int n = nums.size();vector<int> f(n + 1), g(n + 1);f[0] = g[0] = 1;int ret = INT_MIN;for(int i = 1; i <= n; i++){int x = nums[i - 1], y = f[i - 1] * nums[i - 1], z = g[i - 1] * nums[i - 1];f[i] = max(x, max(y, z));g[i] = min(x, min(y, z));ret = max(ret, f[i]);}return ret;}
};结语：今日的刷题分享到这里就结束了，希望本篇文章的分享会对大家的学习带来些许帮助，如果大家有什么问题，欢迎大家在评论区留言~~~
