子数组问题
目录
环形子数组的最大和
乘积最大子数组
乘数为正数的最长子数组长度
等差数列划分
最长湍流子数组
单词拆分
环绕字符串中唯一的子字符串
声明：接下来主要使用动态规划来解决问题！！！
最大子数组和
题目
思路
解决子数组问题，在接下来将屡试不爽的采用“以某个位置为结尾”来分析问题。
状态表示：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& nums) { int n=nums.size(); vector 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& nums) { int n=nums.size(); vector f(n+1); vector 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& nums) { int n=nums.size(); vector f(n+1); vector 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 和 nums[i]<0）。
状态转移方程：
初始化：不用初始化
填表顺序：从左往右。
返回值：f表最大值。
代码
class Solution {public: int getMaxLen(vector& nums) { int n=nums.size(); vector f(n+1); vector g(n+1); for(int i=1;i0){ 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& nums) { int n=nums.size(); if(n<3) return 0; vector 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& arr) { int n=arr.size(); vector f(n,1); vector g(n,1); for(int i=1;iarr[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& wordDict) { unordered_set hash; for(string str:wordDict) hash.insert(str); int n=s.size(); s=\' \'+s; vector dp(n+1); dp[0]=true; for(int i=1;i=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 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; }};
