目录
最大子数组和
环形子数组的最大和
乘积最大子数组
乘数为正数的最长子数组长度
等差数列划分
最长湍流子数组
单词拆分
环绕字符串中唯一的子字符串
声明：接下来主要使用动态规划来解决问题！！！
最大子数组和
题目
思路
解决子数组问题，在接下来将屡试不爽的采用“以某个位置为结尾”来分析问题。
状态表示：dp[i]表示以i位置为结尾的最大子数组和。
我们可以将上面很多情况分为两类：i单独为数组；i和前面的元素一起组成数组。
状态转移方程：dp[i]=max(nums[i],dp[i-1]+nums[i])
初始化：dp[0]=nums[0]。
填表顺序：从左往右。
返回值：dp表的最大值。
代码
class Solution {
public:int maxSubArray(vector<int>& nums) {int n=nums.size();vector<int> dp(n+1);for(int i=1;i<=n;i++)dp[i]=max(nums[i-1],dp[i-1]+nums[i-1]);return *max_element(dp.begin()+1,dp.end()); }
};环形子数组的最大和
题目
思路
本道题差别于上一道题的地方在于，数组是环形的，这样的话，在屡试不爽的采用“以i位置为结尾”来分析问题时，还需要通过%模运算，有点麻烦。
通过分析不难发现，环形子数组的最大和只有两种情况：
其一是最大子数组在数组中间，其二是最大子数组在头和尾。
通过上图不难发现，第一种情况可以采用求“最大子数组”的方式，由于数组的总和是确定的，那么第二种情况可以采用求“最小子数组”的方式。
状态表示：f[i]表示以i位置为结尾的最大子数组的和；
g[i]表示以i位置为结尾的最小子数组的和。
状态转移方程：f[i]=max(nums[i],f[i-1]+nums[i])
g[i]=min(nums[i],g[i-1]+nums[i])
初始化：不用初始化。
填表顺序：从左往右。
返回值：如果sum=gmin，返回fmax；否则，返回max(fmax,sum-gmin)。
代码
class Solution {
public:int maxSubarraySumCircular(vector<int>& nums) {int n=nums.size();vector<int> f(n+1);vector<int> g(n+1);int sum=0;for(int x:nums)sum+=x;for(int i=1;i<=n;i++){f[i]=max(nums[i-1],f[i-1]+nums[i-1]);g[i]=min(nums[i-1],g[i-1]+nums[i-1]);}int fmax=*max_element(f.begin()+1,f.end());int gmin=*min_element(g.begin()+1,g.end());if(gmin==sum) return fmax;else return max(fmax,sum-gmin);}
};乘积最大子数组
题目
思路
解决子数组问题，依旧屡试不爽的采用“以某个位置为结尾”来分析问题。
状态表示：f[i]表示以i位置为结尾的最大子数组和;
g[i]表示以i位置为结尾的最小子数组和。
我们可以将上面很多情况分为两类：i单独为数组；i和前面的元素一起组成数组（又分为nums[i]>0 和 nums[i]<0）。
状态转移方程：
初始化：f[0]=g[0]=0
填表顺序：从左往右
返回值：f表最大值。
代码
class Solution {
public:int maxProduct(vector<int>& nums) {int n=nums.size();vector<int> f(n+1);vector<int> g(n+1);f[0]=g[0]=1;for(int i=1;i<=n;i++){f[i]=max(nums[i-1],max(f[i-1]*nums[i-1],g[i-1]*nums[i-1]));g[i]=min(nums[i-1],min(g[i-1]*nums[i-1],f[i-1]*nums[i-1]));}return *max_element(f.begin()+1,f.end());}
};乘数为正数的最长子数组长度
题目
思路
解决子数组问题，依旧屡试不爽的采用“以某个位置为结尾”来分析问题。
状态表示：f[i]表示以i位置为结尾乘积为正数的最长子数组的长度;
g[i]表示以i位置为结尾乘积为负数的最长子数组的长度。
我们可以将上面很多情况分为两类：i单独为数组（又分为nums[i]>0 和 nums[i]<0）；i和前面的元素一起组成数组（又分为nums[i]>0 和 nums[i]<0）。
状态转移方程：
初始化：不用初始化
填表顺序：从左往右。
返回值：f表最大值。
代码
class Solution {
public:int getMaxLen(vector<int>& nums) {int n=nums.size();vector<int> f(n+1);vector<int> g(n+1);for(int i=1;i<=n;i++){if(nums[i-1]>0){f[i]=f[i-1]+1;g[i]=g[i-1]==0?0:g[i-1]+1;}else if(nums[i-1]<0){f[i]=g[i-1]==0?0:g[i-1]+1;g[i]=f[i-1]+1;}}return *max_element(f.begin()+1,f.end());}
};等差数列划分
题目
思路
解决子数组问题，依旧屡试不爽的采用“以某个位置为结尾”来分析问题。
状态表示：dp[i]表示以i位置元素为结尾的等差数列的个数。
状态转移方程：if(nums[i-2]+nums[i]==2*nums[i-1])
dp[i]=dp[i-1]+1;
初始化：不用初始化
填表顺序：从左往右。
返回值：dp表元素之和。
代码
class Solution {
public:int numberOfArithmeticSlices(vector<int>& nums) {int n=nums.size();if(n<3) return 0;vector<int> dp(n);for(int i=2;i<n;i++){if(nums[i-2]+nums[i]==2*nums[i-1])dp[i]=dp[i-1]+1;}int ret=0;for(int k:dp)ret+=k;return ret;}
};最长湍流子数组
题目
思路
解决子数组问题，依旧屡试不爽的采用“以某个位置为结尾”来分析问题。
状态表示：f[i]表示以i位置元素为结尾，呈“上升”趋势的湍流子数组的长度；
g[i]表示以i位置元素为结尾，呈“下降”趋势的湍流子数组的长度。
状态转移方程：
初始化：全都初始化为1.
返回值：两个表的最大值。
代码
class Solution {
public:int maxTurbulenceSize(vector<int>& arr) {int n=arr.size();vector<int> f(n,1);vector<int> g(n,1);for(int i=1;i<n;i++){if(arr[i]>arr[i-1]) g[i]=f[i-1]+1;else if(arr[i]<arr[i-1]) f[i]=g[i-1]+1; }int a=*max_element(f.begin(),f.end());int b=*max_element(g.begin(),g.end());return max(a,b);}
};单词拆分
题目
思路
解决子数组问题，依旧屡试不爽的采用“以某个位置为结尾”来分析问题。
状态表示：dp[i]表示s字符串[0,i]区间内的子字符串可以拆分出在字典中出现的单词。
状态转移方程：dp[i]=dp[j-1]==true && s的[j,i]区间字符串有在字典中出现。【0<=j<i】
初始化：dp[0]=true
填表顺序：从左往右。
返回值：dp[n].
代码
class Solution {
public:bool wordBreak(string s, vector<string>& wordDict) {unordered_set<string> hash;for(string str:wordDict)hash.insert(str);int n=s.size();s=' '+s;vector<bool> dp(n+1);dp[0]=true;for(int i=1;i<=n;i++){for(int j=i;j>=1;j--){if(dp[j-1] && hash.count(s.substr(j,i-j+1))){dp[i]=true;break;}}}return dp[n];}
};环绕字符串中唯一的子字符串
题目
思路
我们依旧屡试不爽的采用“以某个位置为结尾”来分析问题。
状态表示：dp[i]表示以i位置元素为结尾的子字符串在base中出现的次数。
状态转移方程：
if(s[i-1]+1==s[i] || (s[i-1]=='z' && s[i]=='a'))
dp[i]+=dp[i-1];
初始化：全都初始化为1.
返回值：由于题目中要求统计并返回 s 中有多少 不同非空子串 也在 base 中出现，因此我们需要做“去重”操作，对于两个相同字符，只需统计以该字符结尾在base中出现次数最多的那个即可，然后返回去重后的总和。
代码
class Solution {
public:int findSubstringInWraproundString(string s) {int n=s.size();vector<int> dp(n,1);for(int i=1;i<n;i++)if(s[i-1]+1==s[i] || (s[i-1]=='z' && s[i]=='a'))dp[i]+=dp[i-1];int arr[26];for(int i=0;i<n;i++){arr[s[i]-97]=max(arr[s[i]-97],dp[i]);}int ret=0;for(int i=0;i<26;i++)ret+=arr[i];return ret;}
};
