【动态规划专栏】专题四:子数组问题--------最大子数组和&&环形子数组的最大和

简介: 【动态规划专栏】专题四:子数组问题--------最大子数组和&&环形子数组的最大和


题目一来源:

本题来源为:

Leetcode 53. 最大子数组和

题目1描述

给你一个整数数组 nums ,请你找出一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。

子数组 是数组中的一个连续部分。

算法原理

1.状态表示

经验+题目要求

对于本题而言就是:

dp[i]表示:以i位置为结尾时的所有子数组中的最大和

2.状态转移方程

分两种情况:

i位置本身自己为一个子数组

i位置与之前结合为一个子数组

因此状态方程为:

dp[i]=max(nums[i],dp[i-1]+nums[i])

3.初始化

4.填表顺序

从左往右

5.返回值

整个dp表里的最大值

代码实现

动态规划的代码基本就是固定的四步:

1.创建dp表
2.初始化
3.填表
4.返回值

本题完整代码实现:

class Solution
{
public:
    int maxSubArray(vector<int> &nums)
    {
        //创建dp表
        int n=nums.size();
        vector<int> dp(n+1);
        //初始化
        //填表
        int ret=INT_MIN;
        for(int i=1;i<=n;i++)
        {
            dp[i]=max(nums[i-1],dp[i-1]+nums[i-1]);
            ret =max(ret,dp[i]);
        }
        //返回值
        return ret;
    }
};

题目二来源

本题来源为:

Leetcode918. 环形子数组的最大和

题目二描述

给定一个长度为 n 的环形整数数组 nums ,返回 nums 的非空 子数组 的最大可能和 。

环形数组 意味着数组的末端将会与开头相连呈环状。形式上, nums[i] 的下一个元素是 nums[(i + 1) % n] , nums[i] 的前一个元素是 nums[(i - 1 + n) % n] 。

子数组 最多只能包含固定缓冲区 nums 中的每个元素一次。形式上,对于子数组 nums[i], nums[i + 1], …, nums[j] ,不存在 i <= k1, k2 <= j 其中 k1 % n == k2 % n 。

算法原理

我们可以先分析一下:

这道题在最大子数组上加了可以成环的条件。

解决这道题的关键就是可以将这道题转化成最大子数组和的问题。

子数组成环会有两种情况:

  1. 最大的子数组在中间,我们就要可以直接用最大子数组和的问题解题思路
  2. 最大子数组在首尾相连,我们可以反过来,计算中间那一部分也就是最小子数组和,最后用总和一减就是最大子数组和

1.状态表示

经验+题目要求

对于本题而言就是:

f[i]表示:以i位置为结尾时的所有子数组中的最大和

g[i]表示:以i位置为结尾时的所有子数组中的最小和

2.状态转移方程

分两种情况:

i位置本身自己为一个子数组

i位置与之前结合为一个子数组

因此状态方程为:

int x=nums[i-1];
f[i]= max(x,x+f[i -1]);
fmax = max(fmax,f[i]);
g[i]=min(x,x+ g[i-1]);
gmin = min(gmin, g[i]);
sum += X;

3.初始化

4.填表顺序

从左往右

5.返回值

代码实现

动态规划的代码基本就是固定的四步:

1.创建dp表
2.初始化
3.填表
4.返回值

本题完整代码实现:

class Solution 
{
public:
    int maxSubarraySumCircular(vector<int>& nums) 
    {
         //创建dp表
        int n=nums.size();
        vector<int> f(n+1);
        vector<int> g(n+1);
        int fmax=INT_MIN,gmin=INT_MAX,sum =0;
        //初始化
        //填表
       for(int i=1;i<=n;i++)
       {
           int x=nums[i-1];
           f[i]= max(x,x+f[i -1]);
           fmax = max(fmax,f[i]);
           g[i]=min(x,x+ g[i-1]);
           gmin = min(gmin, g[i]);
           sum += x;
       }
        //返回值
        return sum==gmin?fmax:max(fmax,sum-gmin);
    }
};
相关文章
|
6月前
|
存储 算法
LeetCode刷题---209. 长度最小的子数组(双指针-滑动窗口)
LeetCode刷题---209. 长度最小的子数组(双指针-滑动窗口)
|
机器学习/深度学习 算法
【动态规划刷题 9】最大子数组和 III && 环形子数组的最大和
【动态规划刷题 9】最大子数组和 III && 环形子数组的最大和
|
测试技术
【动态规划刷题 10】最大子数组和 III && 环形子数组的最大和
【动态规划刷题 10】最大子数组和 III && 环形子数组的最大和
|
6月前
|
算法 测试技术
【动态规划专栏】专题四:子数组问题--------最大子数组和&&环形子数组的最大和1
【动态规划专栏】专题四:子数组问题--------最大子数组和&&环形子数组的最大和1
54 1
|
6月前
leetcode-560:和为 K 的子数组
leetcode-560:和为 K 的子数组
52 0
|
6月前
leetcode-2104:子数组范围和
leetcode-2104:子数组范围和
43 0
LeetCode刷题Day03——数组(滑动窗口+螺旋矩阵)
所谓滑动窗口,就是不断的调节子序列的起始位置和终止位置,从而得出我们要想的结果。 滑动窗口也可以理解为双指针法的一种,只不过这种解法更像是一个窗口的移动。 实现滑动窗口,主要确定如下三点:
|
人工智能
LeetCode-2104 子数组范围和
LeetCode-2104 子数组范围和
|
人工智能 算法 C++
每日算法系列【LeetCode 907】子数组的最小值之和
每日算法系列【LeetCode 907】子数组的最小值之和
113 0
|
索引
每日一题[LeetCode 689]三个无重叠子数组的最大和
闲来无事,为了保证日更,从今天开始每天更新一道LeetCode题解。 做题顺序是这样的:随机选择一题“困难”类型的题目。 因本人ACM退役颇久,代码多有疏漏,望多多见谅。