本专栏内容为：算法学习专栏，分为优选算法专栏，贪心算法专栏，动态规划专栏以及递归，搜索与回溯算法专栏四部分。 通过本专栏的深入学习，你可以了解并掌握算法。

💓博主csdn个人主页：小小unicorn
⏩专栏分类：动态规划专栏
🚚代码仓库：小小unicorn的代码仓库🚚
🌹🌹🌹关注我带你学习编程知识

题目一来源：

本题来源为：

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);
    }
};