你好，欢迎阅读我的文章~
个人主页：@Mike
所属专栏：动态规划
53. 最大子数组和
最大子数组和
分析:
使用动态规划解决
状态表示:
1.以某个位置为结尾
2.以某个位置为起点
这里使用以某个位置为结尾，结合题目要求，定义的状态表示为:
dp[i]表示：以i位置为结尾的所有子数组中的最大和。
dp[i]的所有可能有两种情况
(1).子数组长度为1：此时dp[i]=nums[i];
(2).子数组的长度大于1：此时dp[i]应该等于以i-1为结尾的所有子数组中和的最大值再加上nums[i],也就是dp[i-1]+nums[i]。
因为我们求最大值，所以我们对这两种情况取最大值即可
dp[i]=max(nums[i],dp[i-1]+nums[i]);
代码:
class Solution {
public:int maxSubArray(vector<int>& nums) {int n=nums.size();vector<int>dp(n+1);int ans=INT_MIN;for(int i=1;i<=n;i++){dp[i]=nums[i-1];dp[i]=max(dp[i],dp[i-1]+nums[i-1]);ans=max(ans,dp[i]);}return ans;}
};动态规划
环形子数组的最大和
分析:
使用动态规划解决
算法思路：
本题与 最大子数组和 的区别在于，考虑问题的时候不仅要分析 数组内的连续区域 ，还要考
虑 数组首尾相连 的一部分。结果的可能情况分为以下两种：
1.结果在数组的内部，包括整个数组。
2.结果在数组首尾相连的一部分上。
对于第一种情况，我们只需按照最大子数组和的方法做即可。
对于第二种情况，我可以换一种思路，既然不在数组的内部的一段，那么我们求出数组的总和，然后在求出数组内的最小子数组和，数组总和减去数组内的最小子数组和就是首尾相连的最大和。
状态表示：
第二种情况：
g[i]表示：以i为结尾的所有子数组中和的最小值。
状态转移方程：
g[i]的所有可能有以下两种情况：
(1).子数组长度为1：此时g[i]=nums[i]
(2).子数组的长度大于1：此时g[i]应该等于以i-1为结尾的所有子数组中和的最小值再加上nums[i]。也就是g[i-1]+nums[i]。
转移方程为:
g[i]=min(nums[i],g[i-1]+nums[i])
代码：
class Solution {
public:int maxSubarraySumCircular(vector<int>& nums) {int n = nums.size();vector<int> maxx(n + 1);vector<int> g(n + 1);int temp1 = INT_MIN;int temp2 = INT_MAX;int sum=0;for(auto num:nums){sum+=num;}for (int i = 1; i <= n; i++) {maxx[i] = max(nums[i - 1], maxx[i - 1] + nums[i - 1]);temp1 = max(temp1, maxx[i]);}for (int i = 1; i <= n; i++) {g[i] = min(nums[i - 1], g[i - 1] + nums[i - 1]);temp2 = min(temp2, g[i]);if(temp2==sum){return temp1;}}return max(sum-temp2,temp1);//情况1和情况2取最大值}
};
