江苏建设教育协会网站,硬件开发一站式平台,黑客攻击的网站,网站开发框架查询目录
动态规划怎么学#xff1f;
1. 题目解析
2. 算法原理
1. 状态表示
2. 状态转移方程
3. 初始化
4. 填表顺序
5. 返回值
3. 代码编写
写在最后#xff1a; 动态规划怎么学#xff1f;
学习一个算法没有捷径#xff0c;更何况是学习动态规划#xff0c;
跟我…目录
动态规划怎么学
1. 题目解析
2. 算法原理
1. 状态表示
2. 状态转移方程
3. 初始化
4. 填表顺序
5. 返回值
3. 代码编写
写在最后 动态规划怎么学
学习一个算法没有捷径更何况是学习动态规划
跟我一起刷动态规划算法题一起学会动态规划
1. 题目解析
题目链接918. 环形子数组的最大和 - 力扣LeetCode 这道题目巴拉巴拉说了一大堆好像很玄乎的东西我们不管他
抓住题目的核心是要找子数组那找子数组的规则是什么呢
我们直接通过看示例来解读 通过示例二我们可以看出什么叫做环形数组他的头和尾是相连的
所以 5 和 5 可以组成一个子数组。
那我们该怎么做这道题呢
我们可以将它拆解成两个子问题
1. 就是正常求他的最大子数组 2. 因为环形数组的原因我们可以将首尾相连的情况转化成求最小子数组和的情况 2. 算法原理
1. 状态表示
根据我们上面分析的两种情况其实就可以氛围两种状态表示
f [ i ] 表示以 i 为结尾的所有子数组的最大和
g [ i ] 表示以 i 为结尾的所有子数组的最小和
2. 状态转移方程
然后每个状态表示有两种情况一个种情况是自己一种情况是自己加上上一个位置的最大/小和
所以他们的状态转移方程是
f [ i ] max( nums[ i ]nums[ i ] f [ i - 1 ] )
g [ i ] min( nums[ i ]nums[ i ] g[ i - 1] )
3. 初始化
初始化时为了防止越界多加一格然后初始化成0即可
4. 填表顺序
从左往右
5. 返回值
max( f 数组的最大值sum - g 数组的最小值 )
3. 代码编写
class Solution {
public:int maxSubarraySumCircular(vectorint nums) {int n nums.size();vectorint f(n 1);auto g f;for(int i 1; i n; i) {f[i] max(nums[i - 1], nums[i - 1] f[i - 1]);g[i] min(nums[i - 1], nums[i - 1] g[i - 1]);}int fmax INT_MIN;int gmin INT_MAX;int sum 0;for(int i 1; i n; i) fmax max(fmax, f[i]);for(int i 1; i n; i) gmin min(gmin, g[i]);for(auto s : nums) sum s;return fmax 0 ? fmax : max(fmax, sum - gmin);}
};
写在最后
以上就是本篇文章的内容了感谢你的阅读。
如果感到有所收获的话可以给博主点一个赞哦。
如果文章内容有遗漏或者错误的地方欢迎私信博主或者在评论区指出~
