动态规划（七）——子数组系列（求和问题）
♥♥♥~~~~~~欢迎光临知星小度博客空间~~~~~~♥♥♥
♥♥♥零星地变得优秀~也能拼凑出星河~♥♥♥
♥♥♥我们一起努力成为更好的自己~♥♥♥
♥♥♥如果这一篇博客对你有帮助~别忘了点赞分享哦~♥♥♥
♥♥♥如果有什么问题可以评论区留言或者私信我哦~♥♥♥
✨✨✨✨✨✨ 个人主页✨✨✨✨✨✨
这一篇博客我们继续学习动态规划算法，这一篇博客主要涉及子数组系列的动态规划问题~准备好了吗~我们发车去探索动态规划算法的奥秘啦~🚗🚗🚗🚗🚗🚗
目录
最大子数组和
环形子数组的最大和
最大子数组和
最大子数组和
题目要求十分简单，想让我们求解数组最大的连续子数组的和，其中数组元素有正数也有负数，我们结合动态规划思想来解决这个问题~
分析：
1、状态表示
题目要求：求解数组最大的连续子数组的和
结合这里的题目要求+经验：
dp表中的dp[i]表示为以【i】位置为结尾最大子数组和~
2、状态转移方程
我们以离【i】位置最近的状态分析状态转移方程，处理dp表
既然状态表示为： 以【i】位置为结尾最大子数组和~ ，那么第i个位置肯定在子数组中，那么以【i】位置为结尾的最大子数组和长度可能为1，那么就是它本身；以【i】位置为结尾为结尾的最大子数组和长度可能大于1，那么以【i】位置为结尾的最大子数组和就等于以【i-1】位置为结尾的最大子数组和+nums【i】~取两种情况最大值就可以了~
所以状态转移方程为: dp[i] = max(nums[i],dp[i-1]+nums[i])
3、初始化
我们可以看到，状态转移方程里面有i-1，当i=0的时候显然会出现越界的情况，所以我们需要进行初始化
结合前面如果不想初始化太麻烦，我们可以多申请一些空间，我们可以多申请一个空间，并且把这个空间填写正确的数据保证不影响到后面的结果，我们求数组和不希望影响到后面的结果的话，dp【0】影响到的是dp【1】，即dp【1】=max（nums【0】，nums【0】+dp【0】），那么dp【0】应该等于 0~同时要注意下标映射关系~
那么我们初始化结果就是
dp【0】= 0
4、填表顺序
我们这里的逻辑是从前面依次推出后面的，所以填表顺序是从前往后
5、返回结果
这里返回结果是到最大子数组和，最大子数组可能是数组中任何一个位置为结尾的，所以我们返回dp表中最大值即可~
有了前面的分析，代码实现就比较简单了~
代码实现：
//最大子数组和
class Solution
{
public:int maxSubArray(vector<int>& nums){//1、创建dp表int n = nums.size();vector<int> dp(n + 1);//2、初始化dp[0] = 0;int ret = INT_MIN;//3、填表并且更新结果for (int i = 1; i < n + 1; i++){//注意下标映射关系dp[i] = max(dp[i - 1] + nums[i - 1], nums[i - 1]);ret = max(ret, dp[i]);}//4、返回结果return ret;}
};
顺利通过~
小编这里还实现不多开一个空间的初始化代码，感兴趣的小伙伴可以看一看~
class Solution
{
public:int maxSubArray(vector<int>& nums){//1、创建dp表int n = nums.size();vector<int> dp(n);//2、初始化//题目给出子数组至少包含一个元素//那么以0位置为结尾的最大子数组和就是它本身dp[0] = nums[0];int ret = dp[0];//ret初始化为dp[0]//3、填表并且更新结果for (int i = 1; i < n; i++){dp[i] = max(dp[i - 1] + nums[i], nums[i]);ret = max(dp[i], ret);}//4、返回结果return ret;}
};
顺利通过~
环形子数组的最大和
环形子数组的最大和
读题其实可以发现他与前面的题目十分类似，只不过这一道题目是环形数组，那么把它看成一个线性数组最大子数组和下面两种情况~
第一种情况，我们就可以使用第一个题目的思路解决，那么如果子数组和最大是第二种情况呢？分析一下：既然是头尾是最大子数组和，那么中间就是最小子数组和，用整个数组和减去最小子数组和就是我们想要的结果~那么最小子数组和我们使用动态规划思想解决~
知道了方法，接下来我们使用动态规划思想~
分析：
1、状态表示
题目要求：求解环形数组最大的连续子数组的和
结合这里的题目要求+经验+我们的分析，创建两个dp表，一个求最大子数组和，一个求最小子数组和：
dp1表中的dp1[i]表示为以【i】位置为结尾最大子数组和~
dp2表中的dp2[i]表示为以【i】位置为结尾最小子数组和~
2、状态转移方程
我们以离【i】位置最近的状态分析状态转移方程，处理dp1表
既然状态表示为： 以【i】位置为结尾最大子数组和~ ，那么第i个位置肯定在子数组中，那么以【i】位置为结尾的最大子数组和长度可能为1，那么就是它本身；以【i】位置为结尾为结尾的最大子数组和长度可能大于1，那么以【i】位置为结尾的最大子数组和就等于以【i-1】位置为结尾的最大子数组和+nums【i】~取两种情况最大值就可以了~
所以状态转移方程为: dp1[i] = max(nums[i],dp[i-1]+nums[i])
我们以离【i】位置最近的状态分析状态转移方程，处理dp2表
既然状态表示为：以【i】位置为结尾最小子数组和~ ，那么第i个位置肯定在子数组中，那么以【i】位置为结尾的最小子数组和长度可能为1，那么就是它本身；以【i】位置为结尾为结尾的最小子数组和长度可能大于1，那么以【i】位置为结尾的最小子数组和就等于以【i-1】位置为结尾的最小子数组和+nums【i】~取两种情况最小值就可以了~
所以状态转移方程为: dp2[i] = min(nums[i],dp[i-1]+nums[i])
3、初始化
我们可以看到，状态转移方程里面有i-1，当i=0的时候显然会出现越界的情况，所以我们需要进行初始化
结合前面如果不想初始化太麻烦，我们可以多申请一些空间，我们可以多申请一个空间，并且把这个空间填写正确的数据保证不影响到后面的结果，我们求数组和不希望影响到后面的结果的话，dp1【0】影响到的是dp1【1】，即dp1【1】=max（nums【0】，nums【0】+dp1【0】），那么dp1【0】应该等于 0；dp2【0】影响到的是dp2【1】，即dp2【1】=min（nums【0】，nums【0】+dp2【0】），那么dp2【0】应该等于 0~同时要注意下标映射关系~
那么我们初始化结果就是
dp1【0】= 0 ；dp2【0】= 0
4、填表顺序
我们这里的逻辑是从前面依次推出后面的，所以填表顺序是从前往后,两个dp表一起填
5、返回结果
这里返回结果是到最大子数组和，最大子数组可能是情况1，也可能是情况2，情况1的最大子数组和是dp1表中最大值；情况2的最大子数组和是整个数组和减去最小子数组和~
返回两种情况的最大值~
注意：如果整个数组全部是负数，情况2计算结果为0，情况1计算结果为最大的负数，题目要求子数组至少包含一个元素，所以情况1的计算结果才是正确的，进行结果返回的时候需要先判断再返回~
代码实现：
//环形子数组的最大和
class Solution
{
public:int maxSubarraySumCircular(vector<int>& nums){//1、创建dp表int n = nums.size();vector<int> dp1(n + 1);//求解最大子数组和dp表vector<int> dp2(n + 1);//求解最小子数组和dp表//2、初始化dp1[0] = 0, dp2[0] = 0;//3、填表并且更新最大子数组和以及最小子数组和int Max_subarr_sum = INT_MIN;int Min_subarr_sum = INT_MAX;int Sum_arr = 0;for (int i = 1; i < n + 1; i++){//注意下标映射关系dp1[i] = max(dp1[i - 1] + nums[i - 1], nums[i - 1]);Max_subarr_sum = max(dp1[i], Max_subarr_sum);dp2[i] = min(dp2[i - 1] + nums[i - 1], nums[i - 1]);Min_subarr_sum = min(dp2[i], Min_subarr_sum);Sum_arr += nums[i - 1];//统计整个数组和}//4、返回结果//返回两种情况最大值//err——全部为负数是错误的//return max(Sum_arr-Min_subarr_sum,Max_subarr_sum);//正确返回：先判断再返回return Sum_arr == Min_subarr_sum ? Max_subarr_sum : max(Sum_arr - Min_subarr_sum, Max_subarr_sum);}
};
顺利通过~
♥♥♥本篇博客内容结束，期待与各位优秀程序员交流，有什么问题请私信♥♥♥
♥♥♥如果这一篇博客对你有帮助~别忘了点赞分享哦~♥♥♥
✨✨✨✨✨✨个人主页✨✨✨✨✨✨