《算法题讲解指南：动态规划算法--子数组系列》--19.最大子数组和，20.环形子数组的最大和

小叶-duck个人主页❄️个人专栏《Data-Structure-Learning》《C入门到进阶自我学习过程记录》《算法题讲解指南》--优选算法《算法题讲解指南》--递归、搜索与回溯算法《算法题讲解指南》--动态规划算法✨未择之路不须回头已择之路纵是荆棘遍野亦作花海遨游目录19.最大子数组和题目链接题目描述题目示例解法(动态规划)算法思路C算法代码算法总结及流程解析20.环形子数组的最大和题目链接题目描述题目示例解法(动态规划)算法思路C算法代码算法总结及流程解析结束语19.最大子数组和题目链接53. 最大子数组和 - 力扣LeetCode题目描述题目示例解法(动态规划)算法思路1.状态表示对于线性dp我们可以用「经验题目要求」来定义状态表示i.以某个位置为结尾巴拉巴拉;ii.以某个位置为起点巴拉巴拉。这里我们选择比较常用的方式以「某个位置为结尾」结合「题目要求」定义一个状态表示dp[i]表示:以i位置元素为结尾的「所有子数组」中和的最大和。2.状态转移方程dp[i]的所有可能可以分为以下两种i.子数组的长度为1:此时dp[i]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]0即可。4.填表顺序根据「状态转移方程」易得填表顺序为「从左往右」。5.返回值状态表示为「以i为结尾的所有子数组」的最大值但是最大子数组和的结尾我们是不确定的。因此我们需要返回整个dp表中的最大值。C算法代码class Solution { public: int maxSubArray(vectorint nums) { //1、创建dp数组 //2、初始化 //3、通过状态转移方程填表 //4、返回结果 int n nums.size(); vectorint dp(n); dp[0] nums[0]; for(int i 1; i n; i) { dp[i] max(dp[i - 1] nums[i], nums[i]); } int ret INT_MIN; for(int i 0; i n; i) { ret max(ret, dp[i]); } return ret; } };算法总结及流程解析20.环形子数组的最大和题目链接918. 环形子数组的最大和 - 力扣LeetCode题目描述题目示例解法(动态规划)算法思路本题与「最大子数组和」的区别在于考虑问题的时候不仅要分析「数组内的连续区域」还要考虑「数组首尾相连」的一部分。结果的可能情况分为以下两种i.结果在数组的内部包括整个数组;ii.结果在数组首尾相连的一部分上。其中对于第一种情况我们仅需按照「最大子数组和」的求法就可以得到结果记为fmax。对于第二种情况我们可以分析一下i.如果数组首尾相连的一部分是最大的数组和那么数组中间就会空出来一部分;ii.因为数组的总和sum是不变的那么中间连续的一部分的和一定是最小的;因此我们就可以得出一个结论对于第二种情况的最大和应该等于sum-gmin其中gmin表示数组内的「最小子数组和」。两种情况下的最大值就是我们要的结果。但是由于数组内有可能全部都是负数第一种情况下的结果是数组内的最大值(是个负数)第二种情况下的gmin sum 求的得结果就会是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]即可。4.填表顺序:根据状态转移方程易得填表顺序为「从左往右」。5.返回值:a.先找到 f 表里面的最大值 - fmax ;b.找到g表里面的最小值 - gmin ;c.统计所有元素的和-sum;b.返回 sum gmin ? fmax : max(fmax, sum - gmin)。C算法代码class Solution { public: int maxSubarraySumCircular(vectorint nums) { //1、创建dp数组 //2、初始化 //3、通过状态转移方程填表 //4、返回结果 int n nums.size(); int sum 0; for(int i 0; i n; i) { sum nums[i]; } vectorint max_dp(n); vectorint min_dp(n); max_dp[0] min_dp[0] nums[0]; for(int i 1; i n; i) { max_dp[i] max(max_dp[i - 1] nums[i], nums[i]); min_dp[i] min(min_dp[i - 1] nums[i], nums[i]); } int max_ret INT_MIN; int min_ret INT_MAX; for(int i 0; i n; i) { max_ret max(max_ret, max_dp[i]); min_ret min(min_ret, min_dp[i]); } //由于子数组必须不为空如果整个数组全为负数也需要返回值最大的负数 //但此时min_ret就为sum也就说明两边情况不存在最大和这是特殊情况 //如果min_retsum则直接返回max_ret即可 return sum min_ret ? max_ret : max(max_ret, sum - min_ret); } };算法总结及流程解析结束语到此19.最大子数组和20.环形子数组的最大和 这两道算法题就讲解完了。对于最大子数组和问题采用线性DP方法定义dp[i]为以i结尾的子数组最大和通过比较单独取当前元素或与前驱子数组组合来递推求解环形子数组问题则分为两种情况处理普通子数组最大和或跨越首尾的子数组和总和减去最小子数组和需注意全负数时的特殊情况处理。希望大家能有所收获