53. 最大子数组和
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组
是数组中的一个连续部分。
示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
示例 2：
输入：nums = [1]
输出：1
算法思路：
1. 状态表⽰：
对于线性dp ，我们可以⽤「经验+题⽬要求」来定义状态表⽰：
- i. 以某个位置为结尾，巴拉巴拉；
- ii. 以某个位置为起点，巴拉巴拉。
这⾥我们选择⽐较常⽤的⽅式，以「某个位置为结尾」，结合「题⽬要求」，定义⼀个状态表⽰： dp[i] 表⽰：以 i 位置元素为结尾的「所有⼦数组」中和的最⼤和。
2. 状态转移⽅程：
dp[i] 的所有可能可以分为以下两种：
- i. ⼦数组的⻓度为1 ：此时 dp[i] = nums[i] ；
- ii. ⼦数组的⻓度⼤于1 ：此时dp[i] 应该等于以i - 1 做结尾的「所有⼦数组」中和 的最⼤值再加上nums[i] ，也就是dp[i - 1] + nums[i] 。
由于我们要的是「最⼤值」，因此应该是两种情况下的最⼤值，因此可得转移⽅程： dp[i] = max(nums[i], dp[i - 1] + nums[i]) 。
3. 初始化：
可以在最前⾯加上⼀个「辅助结点」，帮助我们初始化。使⽤这种技巧要注意两个点：
- i. 辅助结点⾥⾯的值要「保证后续填表是正确的」；
- ii. 「下标的映射关系」。
在本题中，最前⾯加上⼀个格⼦，并且让 dp[0] = 0 即可。
4. 填表顺序：
根据「状态转移⽅程」易得，填表顺序为「从左往右」。
5. 返回值：
状态表⽰为「以i 为结尾的所有⼦数组」的最⼤值，但是最⼤⼦数组和的结尾我们是不确定的。 因此我们需要返回整个dp 表中的最⼤值。
之前在leetcode的题解上，看到⼀句解释：
⾛完这⼀⽣：如果我和你在⼀起会变得更好，那我们就在⼀起，否则我就丢下你。我回顾我最光辉的 时刻就是和不同⼈在⼀起，变得更好的最⻓连续时刻。
代码
class Solution { public: int maxSubArray(vector<int>& nums) { int n = nums.size(); if(n==1) return nums[0]; vector<int> dp(n+1);//n+1 for (int i = 1; i <= n; i++) { dp[i] = max(nums[i-1], dp[i - 1] + nums[i - 1]); } int ret = INT_MIN;//设置为无穷小 for (int i = 1; i <= n; i++)//dp的0是默认为0，1才是映射的起始位置 ret = max(ret, dp[i]); return ret; } };
918. 环形⼦数组的最⼤和//最大的和
给定一个长度为 n 的环形整数数组 nums ，返回 nums 的非空 子数组 的最大可能和 。
环形数组 意味着数组的末端将会与开头相连呈环状。形式上， nums[i] 的下一个元素是 nums[(i + 1) % n] ， nums[i] 的前一个元素是 nums[(i - 1 + n) % n] 。
子数组 最多只能包含固定缓冲区 nums 中的每个元素一次。形式上，对于子数组 nums[i], nums[i + 1], ..., nums[j] ，不存在 i <= k1, k2 <= j 其中 k1 % n == k2 % n 。
示例 1：
输入：nums = [1,-2,3,-2]
输出：3
解释：从子数组 [3] 得到最大和 3
示例 2：
输入：nums = [5,-3,5]
输出：10
解释：从子数组 [5,5] 得到最大和 5 + 5 = 10
思路：
//连续段的最小值，就可以得出两边的最大值~ 
本题与「最⼤⼦数组和」的区别在于，考虑问题的时候不仅要分析「数组内的连续区域」，还要考 虑「数组⾸尾相连」的⼀部分。结果的可能情况分为以下两种：
- i. 结果在数组的内部，包括整个数组；
- ii. 结果在数组⾸尾相连的⼀部分上。 其中，对于第⼀种情况，我们仅需按照「最⼤⼦数组和」的求法就可以得到结果，记为 fmax 。
对于第⼆种情况，我们可以分析⼀下：
- i. 如果数组⾸尾相连的⼀部分是最⼤的数组和，那么数组中间就会空出来⼀部分；
- ii. 因为数组的总和sum 是不变的，那么中间连续的⼀部分的和⼀定是最⼩的；
因此，我们就可以得出⼀个结论，对于第⼆种情况的最⼤和，应该等于 sum - gmin ，其中 gmin 表⽰数组内的「最⼩⼦数组和」。两种情况下的最⼤值，就是我们要的结果。
但是，由于数组内有可能全部都是负数，第⼀种情况下的结果是数组内的最⼤值（是个负数），第 ⼆种情况下的gmin == sum ，求的得结果就会是0 。若直接求两者的最⼤值，就会是0 。
但 是实际的结果应该是数组内的最⼤值。对于这种情况，我们需要特殊判断⼀下。 由于「最⼤⼦数组和」的⽅法已经讲过，这⾥只提⼀下「最⼩⼦数组和」的求解过程，其实与「最 ⼤⼦数组和」的求法是⼀致的。⽤f 表⽰最⼤和， g 表⽰最⼩和。
1. 状态表⽰：
g[i] 表⽰：以 i 做结尾的「所有⼦数组」中和的最⼩值。
2. 状态转移⽅程：
g[i] 的所有可能可以分为以下两种：
- i. ⼦数组的⻓度为1 ：此时g[i] = nums[i] ；
- ii. ⼦数组的⻓度⼤于1 ：此时g[i] 应该等于以i - 1 做结尾的「所有⼦数组」中和的 最⼩值再加上nums[i] ，也就是g[i - 1] + nums[i] 。
由于我们要的是最⼩⼦数组和，因此应该是两种情况下的最⼩值，因此可得转移⽅程： g[i] = min(nums[i], g[i - 1] + nums[i]) 。
3. 初始化：
可以在最前⾯加上⼀个辅助结点，帮助我们初始化。使⽤这种技巧要注意两个点：
- i. 辅助结点⾥⾯的值要保证后续填表是正确的；
- ii. 下标的映射关系。
在本题中，最前⾯加上⼀个格⼦，并且让g[0] = 0 即可。
4. 填表顺序：
根据状态转移⽅程易得，填表顺序为「从左往右」。
5. 返回值：
a. 先找到 f 表⾥⾯的最⼤值->fmax ；
b. 找到g 表⾥⾯的最⼩值->gmin ；
c. 统计所有元素的和->sum ；
b. 返回 sum == gmin ? fmax : max(fmax, sum - gmin) 。//对特殊情况要有一个判断
代码：
class Solution { public: int maxSubarraySumCircular(vector<int>& nums) { // 1. 创建 dp 表 // 2. 初始化 // 3. 填表 // 4. 返回结果 int n = nums.size(); vector<int> f(n + 1), g(n + 1); int fmax = INT_MIN, gmin = INT_MAX, sum = 0; for (int i = 1; i <= n; i++) { int x = nums[i - 1]; f[i] = max(x, x + f[i - 1]); fmax = max(fmax, f[i]); g[i] = min(x, x + g[i - 1]); gmin = min(gmin, g[i]); sum += x; } return sum == gmin ? fmax : max(fmax, sum - gmin); } };
152.乘积最⼤⼦数组//最大乘积
给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续
子数组
（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
测试用例的答案是一个 32-位 整数。
示例 1:
输入: nums = [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
示例 2:
输入: nums = [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。
思路：
这道题与「最⼤⼦数组和」⾮常相似，我们可以效仿着定义⼀下状态表⽰以及状态转移：
- i. dp[i] 表⽰以 i 为结尾的所有⼦数组的最⼤乘积，
- ii. dp[i] = max(nums[i], dp[i - 1] * nums[i]) ；
由于正负号的存在，我们很容易就可以得到，这样求 dp[i] 的值是不正确的。
因为dp[i - 1] 的信息并不能让我们得到dp[i] 的正确值。⽐如数组[-2, 5, -2] ，⽤上述状态转移得 到的dp数组为[-2, 5, -2] ，最⼤乘积为5 。但是实际上的最⼤乘积应该是所有数相乘，结 果为20 。
究其原因，就是因为我们在求dp[2] 的时候，因为nums[2] 是⼀个负数，因此我们需要的是 「i - 1 位置结尾的最⼩的乘积 （-10） 」，这样⼀个负数乘以「最⼩值」，才会得到真实的 最⼤值。 因此，我们不仅需要⼀个「乘积最⼤值的dp 表」，还需要⼀个「乘积最⼩值的dp 表」。
因为不知道nums[i]的正负
所以就会存在，求 最值（本身，最大*本身，最小*本身）
//来求通式，求值
代码：
class Solution { public: int maxProduct(vector<int>& nums) { int numsSize = nums.size(); vector<int> f(numsSize + 1); vector<int> g(numsSize + 1); f[0] = g[0] = 1; // 初始化,乘初始化为1 int ret = nums[0]; for (int i = 1; i <= numsSize; 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(f[i - 1] * nums[i-1], g[i - 1] * nums[i-1])); //要注意对nums的下标的映射关系 ret=max(ret, f[i]);//取得最大值要赋给ret } return ret; } };
tip:
1.乘积多·初始化为1
2.乘积and和 ： 有时都要设两个dp表 gmin
1567.乘积为正数的最⻓⼦//数组⻓度
给你一个整数数组 nums ，请你求出乘积为正数的最长子数组的长度。
一个数组的子数组是由原数组中零个或者更多个连续数字组成的数组。
请你返回乘积为正数的最长子数组长度。
示例 1：
输入：nums = [1,-2,-3,4]
输出：4
解释：数组本身乘积就是正数，值为 24 。
示例 2：
输入：nums = [0,1,-2,-3,-4]
输出：3
解释：最长乘积为正数的子数组为 [1,-2,-3] ，乘积为 6 。
注意，我们不能把 0 也包括到子数组中，因为这样乘积为 0 ，不是正数。
思路：
//现在是引入g来计算负的dp
经典的以.......结尾dp
继续效仿「最⼤⼦数组和」中的状态表⽰，尝试解决这个问题。
状态表⽰： dp[i] 表⽰「所有以 i 结尾的⼦数组，乘积为正数的最⻓⼦数组的⻓度」。
思考状态转移：对于 i 位置上的 nums[i] ，我们可以分三种情况讨论：
- i. 如果 nums[i] = 0 ，那么所有以i 为结尾的⼦数组的乘积都不可能是正数，此时 dp[i] = 0 ；
- ii. 如果nums[i] > 0 ，那么直接找到dp[i - 1] 的值（这⾥请再读⼀遍 dp[i - 1] 代表的意义，并且考虑如果dp[i - 1] 的结值是0 话，影不影响结果），然后加 ⼀即可，此时 dp[i] = dp[i - 1] + 1 ；
- iii. 如果nums[i] < 0 ，这时候你该悲伤了，因为在现有的条件下，你根本没办法得到此时 的最⻓⻓度。因为乘法是存在「负负得正」的，单单靠⼀个dp[i - 1] ，我们⽆法推导 出dp[i] 的值。
但是，如果我们知道「以 i - 1 为结尾的所有⼦数组，乘积为负数的最⻓⼦数组的⻓ 度」neg[i - 1] ，那么此时的dp[i] 是不是就等于neg[i - 1] + 1 呢？
通过上⾯的分析，我们可以得出，需要两个 dp 表，才能推导出最终的结果。不仅需要⼀个「乘积 为正数的最⻓⼦数组」，还需要⼀个「乘积为负数的最⻓⼦数组」。
代码：
class Solution { public: int getMaxLen(vector<int>& nums) { int n = nums.size(); vector<int> f(n + 1); auto g = f; // 乘积为负的最大长度 f[0] = g[0] = 0; int ret = 0;//求最大长度 //如何对数组中出现的特殊的0进行处理呢 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) {//要用else if来跳过0，不能简单地用else f[i] = g[i - 1] == 0 ? 0 : g[i - 1] + 1; // 乘积为负，长度不计 g[i] = f[i - 1] + 1; } ret = max(ret, f[i]); } return ret; } };
413.等差数列划分//数组个数
如果一个数列 至少有三个元素 ，并且任意两个相邻元素之差相同，则称该数列为等差数列。
例如，[1,3,5,7,9]、[7,7,7,7] 和 [3,-1,-5,-9] 都是等差数列。
给你一个整数数组 nums ，返回数组 nums 中所有为等差数组的 子数组 个数。
子数组 是数组中的一个连续序列。
示例 1：
输入：nums = [1,2,3,4]
输出：3
解释：nums 中有三个子等差数组：[1, 2, 3]、[2, 3, 4] 和 [1,2,3,4] 自身。
示例 2：
输入：nums = [1]
输出：0
思路：
对于dp[i] 位置的元素nums[i] ，会与前⾯的两个元素有下⾯两种情况：
- i. nums[i - 2], nums[i - 1], nums[i] 三个元素不能构成等差数列：那么以nums[i] 为结尾的等差数列就不存在，此时dp[i] = 0 ；
- ii. nums[i - 2], nums[i - 1], nums[i] 三个元素可以构成等差数列：那么以 nums[i - 1] 为结尾的所有等差数列后⾯填上⼀个 nums[i] 也是⼀个等差数列，此时 dp[i] = dp[i - 1] 。但是，因为 nums[i - 2], nums[i - 1], nums[i] 三 者⼜能构成⼀个新的等差数列，因此要在之前的基础上再添上⼀个等差数列，于是 dp[i] = dp[i - 1] + 1 。//相当于多的那个就是 后两个再加上新的组成的
综上所述：状态转移⽅程为：
当： nums[i - 2] + nums[i] != 2 * nums[i - 1] 时， dp[i] = 0
当： nums[i - 2] + nums[i] == 2 * nums[i - 1] 时， dp[i] = 1 + dp[i - 1]
//利用原数组形成了对dp的判断if 条件
//个数介入sum
代码：
class Solution { public: int numberOfArithmeticSlices(vector<int>& nums) { int n = nums.size(); if(n<3) return 0;//要对特例进行一个提前判断，避免溢出 vector<int> dp(n); dp[0] = dp[1] = 0; // dp是以i结尾等差子数组的个数 int sum = 0; // 求的是总共的子数组 for (int i = 2; i < n; i++) { if (nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2]) // 这个地方是对nums数组进行判断 dp[i] = dp[i - 1] + 1; // 多的是以i为结尾，后三位的情况 else dp[i] = 0; // 利用了等差数组具有连续性 sum += dp[i]; } return sum; } };
978.最⻓湍流⼦数组//整体最长
给定一个整数数组 arr ，返回 arr 的 最大湍流子数组的长度 。
如果比较符号在子数组中的每个相邻元素对之间翻转，则该子数组是 湍流子数组 。
更正式地来说，当 arr 的子数组 A[i], A[i+1], ..., A[j] 满足仅满足下列条件时，我们称其为湍流子数组：
若 i <= k < j ：
当 k 为奇数时， A[k] > A[k+1]，且
当 k 为偶数时，A[k] < A[k+1]；
或 若 i <= k < j ：
当 k 为偶数时，A[k] > A[k+1] ，且
当 k 为奇数时， A[k] < A[k+1]。
示例 1：
输入：arr = [9,4,2,10,7,8,8,1,9]
输出：5
解释：arr[1] > arr[2] < arr[3] > arr[4] < arr[5]
示例 2：
输入：arr = [4,8,12,16]
输出：2
思路：
对于i 位置的元素arr[i] ，有下⾯两种情况：
i. arr[i] > arr[i - 1] ：如果i 位置的元素⽐ i - 1 位置的元素⼤，说明接下来 应该去找 i -1 位置结尾，并且 i - 1 位置元素⽐前⼀个元素⼩的序列，那就是 g[i - 1] 。更新 f[i] 位置的值： f[i] = g[i - 1] + 1 ；
ii. arr[i] < arr[i - 1] ：如果i 位置的元素⽐ i - 1 位置的元素⼩，说明接下来 应该去找i - 1 位置结尾，并且 i - 1 位置元素⽐前⼀个元素⼤的序列，那就是 f[i - 1] 。更新 g[i] 位置的值： g[i] = f[i - 1] + 1 ；
iii. arr[i] == arr[i - 1] ：不构成湍流数组。
//等式f g的交替验证了 湍流
- //分为下降态和上升态 f and g
- //都初始化为1，更加方便记长度
代码：
class Solution { public: int maxTurbulenceSize(vector<int>& arr) { int n = arr.size(); //特例的判断 if(n==1) return 1; vector<int> f(n, 1); auto g = f; int ret = 0; for (int i = 1; i < n; i++) { if (arr[i - 1] < arr[i]) f[i] = g[i - 1] + 1; else if (arr[i - 1] > arr[i])//else的细节判断 g[i] = f[i - 1] + 1; ret = max(ret, max(f[i], g[i])); } return ret; } };
139.单词拆分
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。
注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
示例 2：
输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。
注意，你可以重复使用字典中的单词。
示例 3：
输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false
思路：
哈希表优化的⼩细节：
在状态转移中，我们需要判断后⾯部分的⼦串「是否在字典」之中，因此会「频繁的⽤到查询操 作」。为了节省效率，我们可以提前把「字典中的单词」存⼊到「哈希表」中。
代码
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; // j是怎么确定的 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]; } };
总结：
