一、最大子数组和

. - 力扣（LeetCode）

 二、环形子数组的最大和

. - 力扣（LeetCode）

 

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);//有可能数据全是负数
    }
};

三、乘积的最大子数组

. - 力扣（LeetCode）

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());
    }
};

四、乘积为正数的最长子数组

. - 力扣（LeetCode）

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());//第一个位置是不能算上的
    }
};

五、等差数组划分

. - 力扣（LeetCode）

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);
   }
};

六、最长湍流子数组

. - 力扣（LeetCode）

 七、单词拆分

. - 力扣（LeetCode）

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];
    }
};

八、环绕字符串中的唯一子字符串

. - 力扣（LeetCode）

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);
    }
};