题目一来源：
本题来源为：
题目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; } };
题目二来源
本题来源为：
题目二描述
给定一个长度为 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.状态表示
经验+题目要求
对于本题而言就是：
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); } };
