三只松鼠电商网站建设,清涧县住房和成乡建设局 网站,如何创建网站内容,wordpress主题友情链接设置题目链接#xff1a;leetcode环形子数组的最大和 目录
题目解析#xff1a;
算法原理
1.状态表示
2.状态转移方程
3.初始化
4.填表顺序
5.返回值
编写代码 题目解析#xff1a; 题目让我们求返回 nums 的非空 子数组 的最大可能和
这道题如果是按照-这道题-是不对…题目链接leetcode环形子数组的最大和 目录
题目解析
算法原理
1.状态表示
2.状态转移方程
3.初始化
4.填表顺序
5.返回值
编写代码 题目解析 题目让我们求返回 nums 的非空 子数组 的最大可能和
这道题如果是按照-这道题-是不对的因为这道题中是环形数组。 这道题我们可以分情况讨论
1.先按照之前的方法子数组系列_最大子数组和
求出如果不是环形数组那么他的最大和是多少
(求最大和) 2.我们反过来想这里题目求和最大值
如果我们求得这个数组里的连续最小和再用数组总和-最小和---》就可以得到这个数组的最大和
求最小和 算法原理:
1.状态表示
先创建一个dp表 首先先思考dp表里面的值所表示的含义是什么
根据上面的分析我们需要求两中状态的最大和
f[i] 表示:以i 为结尾的所有子数组中的最大和
g[i] 表示:以i为结尾的所有子数组中的最小和 这种状态表示怎么来的
1.经验题目要求
用之前或者之后的状态推导出dp[i][j]的值
根据最近的最近的一步来划分问题 2.状态转移方程
dp[i]等于什么 一、(求最大值f[i]):
这里我们分两种情况讨论
情况一当连续子数组的长度1 那么此时f[i]就应该等于该位置的值即num[i];
所以得f[i]num[i]; 情况一当连续子数组的长度1 此时我们应该用i-1位置的最大和再加上i位置的值num[i]
而“i-1位置的最大和”就是f[i-1]
所以得f[i]f[i-1]num[i] 综上
题目需要最大值所以要取这两者的最大值
即f[i]max(num[i],f[i-1]num[i]) 一、(求最小值g[i]):
同理g[i]min(num[i],g[i-1]num[i]) 3.初始化
(保证填表的时候不越界)
根据状态转移方程我们需要初始化[i-1]
这里我们采用创建虚拟节点的方式 为了不让f[0]影响后续的值
所以f[0]g[0]0;
4.填表顺序
为了填写当前状态的时候所需要的状态已经计算过了
这里所需要的状态是
这里所需要的状态是i-1
所以从左到右 5.返回值
根据题目要求和状态表示
综上分析
如果最小值数组和说明该数组中都是负数
此时只需返回f表里的最大值就可以了
否则就返回数组和-g表里的最小值就可以得到最大值 编写代码: class Solution {
public:int maxSubarraySumCircular(vectorint nums) {//1.创建dp表//2.初始化//3.填表//4.返回结果int nnums.size();vectorint f(n1);auto gf;int rmaxINT_MIN;int rminINT_MAX;int sum0;for(int i1;in1;i){int xnums[i-1];f[i]max(x,f[i-1]x);rmaxmax(f[i],rmax);g[i]min(x,g[i-1]x);rminmin(g[i],rmin);sumnums[i-1];}return sum rmin ? rmax : max(rmax, sum - rmin);}
};
