最大子数组

https://leetcode.cn/problems/maximum-subarray

---

状态表示：dp 表每一个位置表示当前位置的最大子数组的和

状态转移方程推导：首先明确子数组是连续，那么当前位置的子数组最大的和要么是自己，要么是前一个位置的最大子数组的和加上自己，二者区最大值，dp[i] = Max(dp[i-1] + arr[i], dp[i])

初始化：由于要用到前一个状态值，所以在填写第一个状态值的时候会发生越界行为，为了避免这一个行为，我们可以扩大 dp 表，也就是将 dp 表增加一个空位，从下标为 1 的 开始填表，为了不影响后续填表，那么我们需要处理 dp[0] 的数值，dp[1] = MAX（dp[0] + arr[0]， arr[0]) ，因为 dp[0] 表示的是第一个元素的子数组的最大值，这个最大值就是 arr[0]，所以 dp[0] 直接填写为 0 即可
或者你不扩大数组也行，从 下标 1 开始填表，dp[0] = arr[0]，这样就没有数组下标的映射关系的处理

填表顺序：因为从状态转移方程得知，当前的状态值要根据前一个状态值才能获得，所以从左到右依次填表

返回值：我们使用一个变量 ret 来记录当前最大值，然后在填表的过程中顺便比较出当前获得的最大子数组的和。

java">class Solution {public int maxSubArray(int[] nums) {int len = nums.length;int ret = Integer.MIN_VALUE;int[] dp = new int[len+1];for(int i = 1; i <= len; i++) {dp[i] = Math.max(dp[i-1] + nums[i-1], nums[i-1]);ret = Math.max(ret, dp[i]);}return ret;}
}

环形子数组的最大和

https://leetcode.cn/problems/maximum-sum-circular-subarray

---

题目解析：因为是环形数组，所以子数组可能会出现首尾相连的情况，那如何获得首尾相连的子数组的最大值呢？我们可以逆向思考一下，首先如果是首尾相连的子数组的最大值的话，那么剩余部分就不是首尾相连的元素，而这些元素的和就是最小值。
如果我们把求首尾相连的子数组的最大和换成非首尾相连的子数组最小和，这样就好办多了，也就是定义两个状态，一个是该位置的最小子数组和，另一个就是该位置的最大子数组和。使用两个 dp 表

注意事项：如果数组全是负数，最后得到的最小值就是整个数组，也就是这个情况下应该返回 dp 表中求最大子数组和的最大值，因为此时不存在首尾相连的数组了，那么我们就需要顶一个 sum 变量来统计数组所有元素之和，如果最小值和 sum 相同说明整个数组元素都是负数需要返回最大值。

java">class Solution {public int maxSubarraySumCircular(int[] nums) {int len  = nums.length;int[] f = new int[len+1];//大int[] g = new int[len+1];//小int max = Integer.MIN_VALUE;int min = Integer.MAX_VALUE;int sum = 0;for(int i = 1; i <= len; i++) {f[i] = Math.max(f[i-1] + nums[i-1], nums[i-1]);max = Math.max(f[i], max);g[i] = Math.min(g[i-1] + nums[i-1], nums[i-1]);min = Integer.min(min, g[i]);sum += nums[i-1];}return sum == min ? max : Math.max(sum - min, max);}
}

乘积最大子数组

https://leetcode.cn/problems/maximum-product-subarray

---

乘积最大的子数组，我们根据前几题的经验很容易得到， dp[i] = max(dp[i-1] * nums[i], nums[i])

但是由于数组存在负数，所以乘积的结果可能为 负数，假设数组元素为 -2, 1，-3
那么你填写的dp 表就为 -2 1 -3，但是这是不可能的，因为最大的子数组应该是 6（所有元素相乘）
这是为什么呢？因此负数和负数相乘得到的正数你忽略了，首先假设前一个 dp 值为 负数的时候，当前元素为 正数时，得到的 dp 值就是正数本身了。如果当前元素为 负数时，负数乘负数得到的正数一定是要填写的 dp 值。但是由于你的初始 dp 值设置的是最大值，那么就可能会忽略了 dp 值为负数的情况。

因此我们需要使用两个状态标识，一个是当前子数组的乘积的最大值 f，一个是当前子数组乘积的最小值 g
由于可能会出现正数乘正数，负数乘负数，正数乘负数三种情况，我们可以定义三个变量，一个是 该元素本身nums[i]，另一个是 该元素乘以前一个 dp 最小值，nums[i] * g[i-1]，另一个就是 该元素乘以前一个 dp 最大值，nums[i] * f[i-1]

填表 f 表是最大值，g 表是最小值

返回值 ret 和 f 表进行比较，因为是找最大值，所以和 f 表比较寻找

java">class Solution {public int maxProduct(int[] nums) {int len = nums.length;int[] f = new int[len+1];//大int[] g = new int[len+1];//小f[0] = g[0] = 1;int ret = Integer.MIN_VALUE;for(int i = 1; i <= len; i++) {int x = nums[i-1] * f[i-1];int y = nums[i-1] * g[i-1];f[i] = Math.max(nums[i-1], Math.max(x,y));g[i] = Math.min(nums[i-1], Math.min(x,y));ret = Math.max(ret, f[i]);}return ret;} 
}

乘积为正数的最长子数组长度

https://leetcode.cn/problems/maximum-length-of-subarray-with-positive-product

---

由于存在负数乘负数的情况，我们可以定义两个状态：一个是乘积为正数的最大子数组的长度 f 表，另一个则是乘积为负数的最大子数组的长度 g 表。

分类讨论：
如果当前元素为正数：f[i] = f[i-1] + 1
g 表则需要小心一点，因为 g[i-1] 如果等于 0，说明前一个状态不存在负数子数组，则此时 g[i] 应该填写 0，而不是 g[i-1] + 1
当前元素为负数：g[i] = g[i-1] + 1
f 表需要小心，还是一样，如果 g[i-1] 等于 0 的话，说明前一个状态不存在负数的子数组，此时 f[i] = 0，而不是g[i-1] + 1

java">class Solution {public int getMaxLen(int[] nums) {int n = nums.length;int[] f = new int[n+1]; //正数int[] g = new int[n+1]; //负数int ret = 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) {f[i] = (g[i-1] == 0 ? 0 : g[i-1] + 1);g[i] = f[i-1] + 1;}ret = Math.max(ret, f[i]);}return ret;}
}

等差数列划分

https://leetcode.cn/problems/arithmetic-slices

---

等差数列的判断：nums[i] - nums[i-1] == nums[i-1] - nums[i-2]，我们可以使用这一条公式来判断等差数列。

状态表示：当前位置所有的子数组的等差数列的总数

状态转移方程推导：使用等差数列的判断公式，来判断当前元素能否和前一个元素构成等差数列，如果不能，dp 值就为 0；如果能，dp 值应该为 dp[i-1] +1 ，为什么是 dp[i-1] + 1？
首先因为这个元素可以和前两个个元素构成等差数列，那前一个元素构成的等差数列加上这个新元素也还是等差数列，即由前一个元素为结尾构成的等差数列，现在算上新元素的一份，新元素的等差数列个数同样也包含这部分，所以要加上 dp[i-1]。最后要 加 1， 这个 1 是 新元素和前两个元素构成的三个元素的等差数列，这个数列在前面的 dp[i-1] 中是没有包含的，所以要加 上 1，即 dp[i] = dp[i-1] + 1

由于等差数列至少有三个元素，所以我们从数组第三个元素开始寻找。

java">class Solution {public int numberOfArithmeticSlices(int[] nums) {int n = nums.length;if(n < 3) {return 0;}int[] dp = new int[n];int ret = 0;for(int i = 2; i < n; i++) {if(nums[i] - nums[i-1] == nums[i-1] - nums[i-2]) {dp[i] = dp[i-1] + 1;}ret += dp[i];}return ret;}
}

最大湍流子数组

https://leetcode.cn/problems/longest-turbulent-subarray

---

状态表示：以 i 位置为结尾的湍流数组的最大长度
细分状态标识：i 位置的元素和前一个元素有三种关系，首先是 arr[i] > arr[i-1]，那么湍流数组的要求就可能是存在 arr[i-1] < arr[i-2]；第二种情况就是 arr[i] < arr[i-1]，那么湍流数组的要求就可能存在 arr[i-1] > arr[i-2]；最后一种情况就是 arr[i] == arr[i-1]，这种情况湍流数组的长度为 1

由于存在三种情况，我们可以定义两个 dp 表，一个表示以 i 结尾的湍流数组最后一个状态是 下降状态，即 arr[i] < arr[i-1]；另一个 dp 表则表示 以 i 结尾的湍流数组最后一个状态呈现上升状态，即 arr[i] > arr[i-1]。

由于单独一个元素可以构成湍流数组，我们把 dp 都初始化为 1
这样第三种相等的情况就可以不用考虑了。

java">class Solution {public int maxTurbulenceSize(int[] arr) {int n = arr.length;int[] f = new int[n];//下降int[] g = new int[n];//上升int ret = 1;Arrays.fill(f, 1);Arrays.fill(g, 1);for(int i = 1; i < n; 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 = Math.max(ret, Math.max(f[i], g[i]));}return ret;}
}

单词拆分

https://leetcode.cn/problems/word-break

---

状态表示：以 i 位置为结尾的字符串是否可以由字典的单词拼凑

如何判断字符串可以被字典的单词平凑而成 => 首先我们对字符串进行划分，[0, j-1] 和 [ j, i ] 两个字符串，首先必须保证 dp[j-1] == true 才能说明 【0, j-1】的字符串可以被拼凑而成，之后我们才能进入下一步，判断 【j-1，i】这个字符串能否被字典的单词拼凑而成。

如何快速判断字符串是否在字典里？我们使用哈希表保存字典的单词，这样就可以快速查找了。

返回值：dp[n-1]，返回最后一个字符为结尾的字符串能否由字典的单词拼凑而成

java">class Solution {public boolean wordBreak(String s, List<String> wordDict) {Set<String> set = new HashSet<>();for(String x : wordDict) {set.add(x);}int n = s.length();boolean[] dp = new boolean[n+1];s = " " + s;dp[0] = true;for(int i = 1; i <= n; i++) {for(int j = i; j > 0; j--) {if(dp[j-1] && set.contains(s.substring(j, i + 1))) {dp[i] = true;break;}}}return dp[n];}
}

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

https://leetcode.cn/problems/unique-substrings-in-wraparound-string

---

状态表示：以 i 为结尾的所有的子串存在 在 base 中的数量

由于 base 是由 26 个字母顺序构成的环形字符串，所以子串要么是 char(i) - char(i-1) == 1 或者是 char(i) = ‘a’ && char(i-1) == ‘z’ 这两种情况。

由于子串也会出现重复的情况，我们需要进行去重操作，由于是 26 个小写字母，我们可以构建一个数组，保存以 该字母为结尾的子串的最大数量即可。然后遍历求和返回即可。

java">class Solution {public int findSubstringInWraproundString(String s) {int n = s.length();int[] dp = new int[n];Arrays.fill(dp, 1);for(int i = 1; i < n; i++) {if(s.charAt(i) - s.charAt(i-1) == 1 || s.charAt(i) == 'a' && s.charAt(i-1) == 'z') {dp[i] = dp[i-1] + 1;}}int[] arr = new int[26];int ret = 0;for(int i = 0; i < n; i++) {arr[s.charAt(i) - 'a'] =  Math.max(dp[i], arr[s.charAt(i) - 'a']); //去重}for(int i = 0; i < 26; i++) {ret += arr[i]; }return ret;}
}