泰州网站制作网站,wordpress 获取总页数,wordpress设置缓存,开封网站建设兼职个人主页 #xff1a; 个人主页 个人专栏 #xff1a; 《数据结构》 《C语言》《C》《算法》 文章目录 前言一、题目解析二、解题思路解题思路状态表示状态转移方程初始化填表顺序返回值 三、代码实现总结 前言
本篇文章仅是作为小白的我的一些理解#xff0c;#xff0c;… 个人主页 个人主页 个人专栏 《数据结构》 《C语言》《C》《算法》 文章目录 前言一、题目解析二、解题思路解题思路状态表示状态转移方程初始化填表顺序返回值 三、代码实现总结 前言
本篇文章仅是作为小白的我的一些理解如果有错误的地方希望大佬们指出。 918. 环形子数组的最大和
一、题目解析 求环型数组中连续子数组最大和。
二、解题思路
解题思路
关于子数组的最大和其有两种情况。 对于情况1而言我们只需要正常使用dp求最大子数组和即可。 对于情况2而言如果我们使用前缀和 与 后缀和 求和来求最大子数组和就相对麻烦但如果我们先求最小子数组和呢
情况二求最大子数组和就可以转换为数组和(sum) - 最小子数组和。
状态表示
该题的状态表示经验(以该位置为终点 / 以该位置为起点) 题目要求 那么对于情况1记为 f() f [ i ]表示以 i 位置为终点的所以子数组的最大和。 那么对于情况2记为 g()g [ i ]表示以 i 位置为终点的所以子数组的最小和。
状态转移方程
情况1 对于在数组 i 位置的元素我们可以将其分成两个状态。
即 f [i]的长度等于1和 f [i]的长度大于1。 当 f [i]的长度等于1时此时子数组最大和不就是该元素的大小即f [i] nums[i] 当 f [i]的长度大于1时此时子数组最大和不就是 之前子数组最大和(f[i-1]) 该元素大小即f[i] f[i-1] nums[i] 那么我们对这两种情况取最大值即可得 f [ i ] 的状态转移方程。
情况2 和情况1类似对于情况2我们同样可以以 i位置分成两种状态。 即 g [i]的长度等于1和 g [i]的长度大于1。 当 g [i]的长度等于1时此时子数组最小和不就是该元素的大小即g [i] nums[i] 当 g [i]的长度大于1时此时子数组最小和不就是 之前子数组最小和(g[i-1]) 该元素大小即g[i] g[i-1] nums[i] 那么我们对这两种状态取最小值既可以得到 g [i]的状态转移方程
初始化
我们要求 f [i]就要先知道 f [i -1]但如果当 i 0时f [i-1]就会越界。那么我们虚拟一块空间将整个 f[i] 后移一个位置。如下所示 如果我们进行这样的操作有两点需要注意。
如何填写 f[0]保证后续填表结果正确 只要f[0] 0即可毕竟f[1] max(f[0], f[0]nums[0])此时f[0] f[0] nums[0]映射关系 因为整个f[i]后移了一个所以f[i] 所对应的元素 nums[i]相对前移了即f[i] 与 nums[i-1]的元素相对应。
填表顺序
要求f[i]就要先知道f[i-1]那么我们就要从前向后遍历数组nums来填表。
返回值
我们只需要 返回情况1 与 情况2 的最大值即可。 但对于{-1, -2, -3, -4}而言情况2 的值是sum(-10) - gmin(-10)等于0情况1 的值是fmax(-1)。那么返回值就是0结果错误。所以要先判断gmin sum如果相等表示此时数组全是负数返回fmax即可。如果不相等返回情况1 与 情况2 的最大值即可。
三、代码实现
class Solution {
public:int maxSubarraySumCircular(vectorint nums) {int n nums.size();vectorint f(n1), g(n1);int fmax INT_MIN, gmin INT_MAX, sum 0;for(int i 1; i n; i){f[i] max(f[i-1] nums[i-1], nums[i-1]);fmax max(f[i], fmax);g[i] min(g[i-1] nums[i-1], nums[i-1]);gmin min(g[i], gmin);sum nums[i-1];}return sum gmin? fmax: max(fmax, sum - gmin);}
};总结
以上就是我对于环形子数组的最大和的理解。感谢支持
