DP：子数组模型
一、最大子数组和
二、环形子数组的最大和
class Solution {
public:
int maxSubarraySumCircular(vector<int>& nums)
{
//动态规划思想解决
//环形数组问题，尝试转化成普通数组
int n=nums.size();
vector<int> f(n);
f[0]=nums[0];
auto g=f;
for(int i=1;i<n;++i)
{
f[i]=max(nums[i],f[i-1]+nums[i]);//最大
g[i]=min(nums[i],g[i-1]+nums[i]);//最小
}
int fmax=*max_element(f.begin(),f.end());
int gmin=*min_element(g.begin(),g.end());
int sum=accumulate(nums.begin(),nums.end(),0);
return sum==gmin?fmax:max(fmax,sum-gmin);//有可能数据全是负数
}
};三、乘积的最大子数组
class Solution {
public:
int maxProduct(vector<int>& nums)
{
//动态规划思想解决
//负负得正可能更大
//所以需要两个dp表示 一个是最大，一个是最小
int n=nums.size();
vector<int> f(n);
f[0]=nums[0];
auto g=f;
for(int i=1;i<n;++i)
{
int x=nums[i];
if(x>0)
{
f[i]=max(x,x*f[i-1]);
g[i]=min(x,x*g[i-1]);
}
else
{
f[i]=max(x,x*g[i-1]);
g[i]=min(x,x*f[i-1]);
}
}
return *max_element(f.begin(),f.end());
}
};四、乘积为正数的最长子数组
class Solution {
public:
int getMaxLen(vector<int>& nums)
{
//动态规划思想解决
//负负得正可能更大
//所以需要两个dp表示 一个是为正最长，一个是为负最小
int n=nums.size();
vector<int> f(n+1);//f[i]表示到i位置时乘积为正数的最长子数组长度
auto g=f;//g[i]表示到i位置时乘积为负数的最长子数组长度
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; //如果前面是0，那么这个数还是正数的话g[i]=0
}
else if(nums[i-1]<0)
{
f[i]=g[i-1]==0?0:g[i-1]+1;//如果前面是0，那么这个数还是负数，f[i-1]就还是0
g[i]=f[i-1]+1;
}
//else 本来就是0
//f[i]=g[i]=0;
}
return *max_element(f.begin()+1,f.end());//第一个位置是不能算上的
}
};五、等差数组划分
class Solution {
public:
int numberOfArithmeticSlices(vector<int>& nums)
{
int n=nums.size();
vector<int> dp(n);
for(int i=2;i<n;++i)
if(nums[i]+nums[i-2]==nums[i-1]*2) dp[i]=dp[i-1]+1;
return accumulate(dp.begin(),dp.end(),0);
}
};六、最长湍流子数组
七、单词拆分
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict)
{
// 优化?：将字典??的单词存在哈希表??
unordered_set<string> hash;
for(auto& s : wordDict) hash.insert(s);
int n=s.size();
vector<bool> dp(n+1);
dp[0]=true;//确保后面填表是正确的
s=' '+s;//在字符串前加一个空格，确保dp表和s的下标映射是一样的
//在动规涉及到子串问题常用的技巧
for(int i=1;i<=n;++i)//开始填表
{
for(int j=i;j>=1;--j) //找到第一个满足要求的位置
{
if(dp[j-1]==true&&hash.count((s.substr(j,i-j+1))))
{
dp[i]=true;
break;
}
}
}
return dp[n];
}
};八、环绕字符串中的唯一子字符串
class Solution {
public:
int findSubstringInWraproundString(string s)
{
//dp[i]表示以i位置结尾有多少子串在base中出现
int n=s.size();
vector<int> dp(n,1);
for(int i=1;i<n;++i)//开始填表
if((s[i]-s[i-1]+26)%26==1) //说明符合要求
dp[i]=dp[i-1]+1;
//但是得去重 （y z a b c 和 a b c）
// 2. 计算每?个字符结尾的最?连续?数组的?度
//相同字符的dp值，我们取最大的
vector<int> hash(26);
for(int i=0;i <n; ++i) hash[s[i] - 'a'] = max(hash[s[i]-'a'], dp[i]);
// 3. 将所有结果累加起来
return accumulate(hash.begin(), hash.end(), 0);
}
};本文参与?腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2024-04-10，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录