动态规划——子数组问题
目录
一、最大子数组和
二、环形子数组的最大和
三、乘积最大子数组
四、乘积为正数的最长子数组长度
五、等差数列划分
六、最长湍流子数组
七、单词拆分
八、环绕字符串中唯一的子字符串
一、最大子数组和
最大子数组和
第一步：确定状态表示
dp[i]：表示以 i 位置元素为结尾的所有子数组中，和最大的数组的和。
第二步：推出状态转移方程
第三步：初始化dp表，dp[0] = nums[0]。
填表顺序为从左向右依次填写，最后的返回值是dp表中的最大值。
解题代码：
class Solution
{
public:int maxSubArray(vector<int>& nums) {int m = nums.size();vector<int> dp(m);dp[0] = nums[0];int ret = nums[0];for(int i = 1; i < m; i++){int x = nums[i];int y = dp[i-1] + nums[i];dp[i] = max(x, y);ret = max(ret, dp[i]);}return ret;}
};
二、环形子数组的最大和
环形子数组的最大和
其实，这道题有一个关键的点，就是它是一个环形数组，也就是说，最后一个元素和第一个元素是挨在一起的，它们也能组成一个数组。
给一个环形数组，让找子数组最大和。子数组可能是中间连续部分（示例1），包括自己本身也是子数组。子数组可能是绕一圈形成的（示例2）。
如果直接就在环形数组上面进行处理，有很多边界问题需要考虑。而前面我们做过一道题打家劫舍II也是一个环形的数组，那里我们是将打家劫舍II转换成普通的打家劫舍问题。
所以，这道题我们可以将一个环形数组转换成一个普通数组，来解决。
这样，这道题就转换成了，求子数组和最大值，求子数组和最小值，两个问题都和环形无关了。 用数组总和减去这个最小值就是两端最大值。最后返回这两种情况的最大值就好了。
分析完成，下面就用动态规划思想解决这道题。
第一步：确定状态表示
f[i]：表示以 i 位置元素为结尾的所有子数组中，和最大的数组的和。
g[i]：表示以 i 位置元素为结尾的所有子数组中，和最小的数组的和。
第二步：推出状态转移方程
第三步：初始化dp表
f[0] = g[0] = nums[0]。返回值就是 f 表的最大值和数组总和减去 g 表中的最小值，这两个值中的最大值。
第四步：特殊情况处理
解题代码：
class Solution
{
public:int maxSubarraySumCircular(vector<int>& nums) {int m = nums.size();if(m == 1)return nums[0];vector<int> f(m);vector<int> g(m);int sum = nums[0], fmax = INT_MIN, gmin = INT_MAX;f[0] = nums[0];g[0] = nums[0];for(int i = 1; i < m; i++){f[i] = max(nums[i], f[i-1] + nums[i]);g[i] = min(nums[i], g[i-1] + nums[i]);fmax = max(f[i], fmax);gmin = min(g[i], gmin);sum += nums[i];}return sum == gmin ? fmax : max(fmax, sum - gmin);}
}; 
三、乘积最大子数组
乘积最大子数组
第一步：确定状态表示
f[i]：表示以 i 位置元素为结尾的所有子数组中最大乘积。
g[i]：表示以 i 位置元素为结尾的所有子数组中最小乘积。
第二步：推出状态转移方程
第三步：初始化dp表，f[0] = g[0] = nums[0]。最后的返回值就是 f 表中的最大值。
解题代码：
class Solution
{
public:int maxProduct(vector<int>& nums) {int m = nums.size();vector<int> f(m);vector<int> g(m);f[0] = nums[0], g[0] = nums[0];int ret = nums[0];for(int i = 1; i < m; i++){f[i] = max(nums[i], max(f[i-1]*nums[i], g[i-1]*nums[i]));g[i] = min(nums[i], min(f[i-1]*nums[i], g[i-1]*nums[i]));ret = max(ret, f[i]);}return ret;}
};
四、乘积为正数的最长子数组长度
乘积为正数的最长子数组长度
第一步：确定状态表示
f[i]：表示以 i 位置元素为结尾所有子数组中乘积为正数的子数组的最大长度。
g[i]：表示以 i 位置元素为结尾所有子数组中乘积为负数的子数组的最大长度。
第二步：推出状态转移方程
第三步：初始化dp表，我们应该根据nums数组中第一个元素的正负去初始化dp表。
解题代码：
class Solution
{
public:int getMaxLen(vector<int>& nums) {int n = nums.size();vector<int> f(n); // 乘积为正vector<int> g(n); // 乘积为负if(nums[0] > 0){f[0] = 1;g[0] = 0;}else if(nums[0] < 0){f[0] = 0;g[0] = 1;}int ret = f[0];for(int i = 1; i < n; i++){if(nums[i] > 0){f[i] = f[i-1] + 1;g[i] = g[i-1] == 0 ? 0 : g[i-1] + 1;}else if(nums[i] < 0){g[i] = f[i-1] + 1;f[i] = g[i-1] == 0 ? 0 : g[i-1] + 1;}ret = max(ret, f[i]);}return ret;}
}; 
五、等差数列划分
等差数列划分
第一步：确定状态表示
dp[i]：表示以 i 位置元素为结尾的子数组中，是等差数列的子数组的个数。
第二步：推出状态转移方程
这道题是求是等差数列的子数组的个数，要判断能否构成等差数列，我们需要知道 i 位置元素的前两个元素，来判断这三个元素能否构成等差数列。
如果 i，i-1，i-2 位置元素能构成一个等差数列，那就是在以 i-1，i-2 位置元素为结尾的等差数列后面在加一个 i 位置元素，这些数列也是构成一个等差数列，以 i-1，i-2 位置元素为结尾就相当于以 i-1 位置元素为结尾，而以 i-1 位置元素为结尾的等差数列的个数，就在dp[i-1]里存着。
i，i-1，i-2 位置元素也能构成一个等差数列，所以个数要加1。
如果 i，i-1，i-2 位置元素不能构成一个等差数列，那么就没有以 i 位置元素为结尾的等差数列。
第三步：初始化dp表
因为等差数列要求元素个数不少于三个，所以前两个元素怎么也无法构成等差数列。因此 dp[0] = dp[1] = 0。
返回值就是dp表中所有元素的和。
解题代码：
class Solution
{
public:int numberOfArithmeticSlices(vector<int>& nums) {int m = nums.size();vector<int> dp(m);int ret = 0;for(int i = 2; i < m; i++){if(nums[i-1] - nums[i-2] == nums[i] - nums[i-1])dp[i] = dp[i-1] + 1;elsedp[i] = 0;ret += dp[i];}return ret;}
}; 
六、最长湍流子数组
最长湍流子数组
第一步：确定状态表示
f[i]：表示以 i 位置元素为结尾的所有子数组中，最后呈现 “上升” 状态下的最长湍流数组的长度。
g[i]：表示以 i 位置元素为结尾的所有子数组中，最后呈现 “下降” 状态下的最长湍流数组的长度。
第二步：推出状态转移方程
第三步：初始化dp表
根据示例3，只含有一个元素的数组也可以是湍流子数组，且它既可以是上升的，也可以是下降的。所以nums数组中的任意一个元素都可以单独成为一个湍流数组，所以以 i 位置元素为结尾的湍流子数组的最大长度至少是1。
因此，可以将两个表的元素都初始化为1。返回值就是两表中的最大值。
解题代码：
class Solution
{
public:int maxTurbulenceSize(vector<int>& arr) {int m = arr.size();vector<int> f(m, 1);vector<int> g(m, 1);f[0] = g[0] = 1;int ret = 1;for(int i = 1; i < m; i++){if(arr[i] > arr[i-1])f[i] = g[i-1] + 1;else if(arr[i] < arr[i-1])g[i] = f[i-1] + 1;ret = max(max(f[i], g[i]), ret);}return ret;}
}; 
七、单词拆分
单词拆分
第一步：确定状态表示
dp[i]：表示[0，i] 区间内的字符串，能否被字典中的单词拼接而成。这是一个bool类型的dp表。
第二步：推出状态转移方程
i 位置的字符一定是最后一个单词的成员，那最后一个单词是什么样子呢？可能该字符单独就是最后一个单词，或者往前几位的字符然后和 i 位置字符共同组成一个单词。
这样就可以把[0，i]位置的字符串划分成两部分，前面部分字符串加上最后一个单词。但是我们并不知道最后一个单词起始位置在哪里，因此设 j 为最后一个单词的起始位置。（0 <= j <= i)
第三步：初始化dp表
如果s的第一个字符在字典中，那么 dp[0] = true，否则就是false。返回值就是dp表中的最后一个元素。
解题代码：
class Solution
{
public:bool wordBreak(string s, vector<string>& wordDict) {int m = s.size();unordered_set<string> hash(wordDict.begin(), wordDict.end());vector<bool> dp(m, false);if(hash.count(s.substr(0, 1)))dp[0] = true;for(int i = 1; i < m; i++){for(int j = i; j >= 0; j--){if(j == 0){if(hash.count(s.substr(j, i-j+1))){dp[i] = true;break;}}else if(dp[j-1] && hash.count(s.substr(j, i-j+1))){dp[i] = true;break;}}}return dp[m-1];}
}; 
八、环绕字符串中唯一的子字符串
环绕字符串中唯一的子字符串
第一步：确定状态表示
dp[i]：表示在字符串s中，以 i 位置字符为结尾的所有子字符串中，在base字符串中出现过的字符串的个数。
第二步：推出状态转移方程
以 i 位置字符为结尾的子串有两种情况，该位置字符单独本身就是一个子串，以及和前面元素结合构成子串。
该位置字符单独本身就是一个子串。那么它在base中出现的次数就是1。
该位置字符和前面的字符结合构成子串。i 字符之前的子串，都是以 i - 1 位置字符为结尾形成的子串，那先找到以 i - 1 位置元素为结尾所有子串在base中出现的次数，然后再加上 i 位置元素构成子串，看新的子串在base中出现的次数就可以了。而dp[i-1] 就是以 i - 1位置元素为结尾所有子串在base中出现的次数。然后如果 i 位置元素s[i - 1] == s[i] || (s[i - 1] == z && s[i] ==a)说明以 i 位置结束的字符串也在base中出现了，出现次数是dp[i - 1]。
第三步：初始化dp表
因为每个单独的字符一定在base中出现过，所以可以把dp表里面的值都初始化为1。之后，我们只需要考虑情况二就可以了。
第四步：确定返回值
题目要求返回 s 中有多少不同非空子串在 base 中出现次数，而 dp[i] 表示以 i 位置元素为结尾的所有子串里面，有多少个在base中出现。因此返回 dp 表里面所有元素的和。
但是，我们看一看题目示例2的情况。
dp表里的值之和是3，但是题目要求是不同的子串，返回值应该是2，所以 ['c'] 和 ['c'] 就重复了，因此我们要对结果去重。
去重方法：创建一个大小为26的数组，数组中存储以下标对应的字母为结尾的所有子串中，最大的dp值。最后的返回值，就是数组所有元素的和。
解题代码：
class Solution
{
public:int findSubstringInWraproundString(string s) {int m = s.size();vector<int> dp(m, 1);for(int i = 1; i < m; i++){if((s[i-1] + 1 == s[i]) || (s[i-1] == 'z' && s[i] == 'a'))dp[i] += dp[i-1];}int hash[26] = {0};for(int i = 0; i < m; i++)hash[s[i] - 'a'] = max(dp[i], hash[s[i] - 'a']);int ret = 0;for(int i = 0; i < 26; i++)ret += hash[i];return ret;}
}; 