【学会动态规划】环形子数组的最大和(20)

简介: 【学会动态规划】环形子数组的最大和(20)

动态规划怎么学?

学习一个算法没有捷径,更何况是学习动态规划,

跟我一起刷动态规划算法题,一起学会动态规划!

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(vector<int>& nums) {
        int n = nums.size();
        vector<int> 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);
    }
};

写在最后:

以上就是本篇文章的内容了,感谢你的阅读。

如果感到有所收获的话可以给博主点一个哦。

如果文章内容有遗漏或者错误的地方欢迎私信博主或者在评论区指出~

相关文章
|
6月前
|
算法 测试技术 C++
【动态规划】【滑动窗口】【C++算法】 629K 个逆序对数组
【动态规划】【滑动窗口】【C++算法】 629K 个逆序对数组
|
算法
【学会动态规划】最小路径和(9)
【学会动态规划】最小路径和(9)
41 0
|
测试技术
【动态规划刷题 10】最大子数组和 III && 环形子数组的最大和
【动态规划刷题 10】最大子数组和 III && 环形子数组的最大和
|
机器学习/深度学习 算法
【动态规划刷题 9】最大子数组和 III && 环形子数组的最大和
【动态规划刷题 9】最大子数组和 III && 环形子数组的最大和
|
6月前
|
机器学习/深度学习 算法
【动态规划专栏】专题四:子数组问题--------最大子数组和&&环形子数组的最大和
【动态规划专栏】专题四:子数组问题--------最大子数组和&&环形子数组的最大和
59 1
|
6月前
|
算法 测试技术
【动态规划专栏】专题四:子数组问题--------最大子数组和&&环形子数组的最大和1
【动态规划专栏】专题四:子数组问题--------最大子数组和&&环形子数组的最大和1
54 1
|
1月前
|
存储
【动态规划】子数组系列
本文介绍了多个动态规划问题及其解决方案,包括最大子数组和、环形子数组的最大和、乘积最大子数组、乘积为正数的最长子数组长度、等差数列划分、最长湍流子数组、单词拆分及环绕字符串中唯一的子字符串。通过详细的状态定义、转移方程和代码实现,帮助读者理解每类问题的核心思路与解题技巧。
49 2
|
1月前
|
算法 C++
【算法】双指针+二分(C/C++
【算法】双指针+二分(C/C++
|
5月前
|
存储 算法 数据可视化
LeetCode 题目 97:动态规划、递归到广度优先搜索BFS 实现交错字符串
LeetCode 题目 97:动态规划、递归到广度优先搜索BFS 实现交错字符串
|
6月前
|
人工智能 算法 测试技术
map|动态规划|单调栈|LeetCode975:奇偶跳
map|动态规划|单调栈|LeetCode975:奇偶跳