1. 最大子数组和
状态表示:以 i 位置为结尾时的所有子数组中的最大和
状态转移方程:
i 位置为结尾的子数组又可以分为长度为 1 的和大于 1 的,长度为 1 就是 nums[i] ,长度不为 1 就是 dp[i - 1] + nums[i],最后取这两个的最大值即可
初始化:可以多开一个元素,为了不影响后续的值默认为 0 即可,也可以单独对 dp[0] 进行初始化,就不用多开一个元素了
填表顺序:从左到右
返回值:整个 dp 表中的最大值,因为结果可能是以任意位置结尾的,如果多开一个元素的话最后取最大值就不能再带上这个值了
class Solution { public int maxSubArray(int[] nums) { int n = nums.length; int[] dp = new int[n + 1]; //dp[0] = Math.max(0,nums[0]); int res = -0x3f3f3f; for(int i = 1;i <= n;i++){ dp[i] = Math.max(nums[i - 1],dp[i - 1] + nums[i - 1]); res = Math.max(res,dp[i]); } return res; } }
2. 环形子数组的最大和
这道题和上道题不同的就是是一个环形结构,首尾可以相连,这就会有下面两种情况
情况一和上一题是一样的,就是正常的求最大的子序列和,情况二就是首尾相连的情况,可以转化为求中间部分最小的子序列和,再用总的数组和减去这部分最小的子序列和就是最大子序列和,这两种情况求最大值就可以了
状态表示和状态转移方程都和上一题是类似的
初始化:求最大子序列和时还是 dp[0] 初始化为 0,不过求最小子序列就不一样了
dp[i] = Math.min(nums[i - 1],dp[i - 1] + nums[i - 1]);
求 dp[1] 时需要让最后的结果等于 num[0],所以 dp[i - 1] 就需要设为 0 或者一个很大的数,不过不能设为 int 的最大值,不然可能会溢出
返回值:返回两种情况的最大值,不过有一种情况需要注意,当数组中全是负数的话,第一种情况求的就是负数,第二种情况求的最小值就是整个数组和,再用数组和减去这个最小值就是 0 ,代表什么都不选,肯定是比第一种情况大的,这个时候还是需要返回第一种情况的值
class Solution { public int maxSubarraySumCircular(int[] nums) { int n = nums.length; int[] dp = new int[n + 1]; int ret1 = Integer.MIN_VALUE; int sum = 0; for(int i = 1;i <= n;i++){ dp[i] = Math.max(nums[i - 1],dp[i - 1] + nums[i - 1]); ret1 = Math.max(ret1,dp[i]); sum += nums[i - 1]; } int ret2 = Integer.MAX_VALUE; dp[0] = 0x3f3f3f; for(int i = 1;i <= n;i++){ dp[i] = Math.min(nums[i - 1],dp[i - 1] + nums[i - 1]); ret2 = Math.min(ret2,dp[i]); } if(sum == ret2) return ret1; return Math.max(ret1,sum - ret2); } }
3. 乘积最大子数组
这道题求的是乘积最大的子数组,由于是乘法,就意味着两个负数乘完之后也会变成整数
状态表示:先定义为以 i 位置为结尾时的所有子数组中的最大乘积发现,如果是负数的话也可以乘进来,所以可以定义两个状态
以 i 位置为结尾时的所有子数组中的最大乘积
以 i 位置为结尾时的所有子数组中的最小乘积
状态转移方程:
求 f[i] 时,如果说当前元素是一个负数,那么就需要乘上一个最小的负数,也就是 g[i - 1],如果是正数的话正常求前一个状态的最大值再乘当前元素就行,最终确定最大值时需要再加上当前元素,这三个数一起求一个最大值即可
同理,求最小值 g[i] 时,如果说当前元素是一个正数,那么就需要乘上一个最小的负数,也就是 g[i - 1],如果是负数的话就需要找一个最大的正数来乘,最终确定最小值时需要再加上当前元素,这三个数一起求一个最小值即可
初始化:把 f[0] 和 g[0] 设置为 1 就不影响后续的乘积赋值
填表顺序:从左到右
返回值:f 表中的最大值
class Solution { public int maxProduct(int[] nums) { int n = nums.length; int[] f = new int[n + 1]; int[] g = new int[n + 1]; f[0] = 1; g[0] = 1; int ret = Integer.MIN_VALUE; for(int i = 1;i <= n;i++ ){ f[i] = Math.max(Math.max(nums[i - 1], f[i - 1] * nums[i - 1]), g[i - 1] * nums[i - 1]); g[i] = Math.min(Math.min(nums[i - 1], f[i - 1] * nums[i - 1]), g[i - 1] * nums[i - 1]); ret = Math.max(ret,f[i]); } return ret; } }
4. 乘积为正数的最长子数组长度
状态表示:
f[i]:以 i 位置为结尾的所有子数组中乘积为正数的最长长度
g[i]:以 i 位置为结尾的所有子数组中乘积为负数的最长长度
状态转移方程:
还是和之前一样,可以分为长度为 1 的和长度大于 1 的,当长度为 1 时又可以分为 nums[i] 是正数还是负数两种情况,当是正数时长度就是 1,负数时就是 0,再看长度大于 1 的,也可以分为 nums[i] 是正数还是负数两种情况,当 num[i] 是正数时,就是从以 i - 1 为结尾时数组中的乘积为正数的最长长度加 1 即可,也就是 f[i - 1] + 1,当 num[i] 是负数时,就需要在 i - 1 为结尾时数组中的乘积为负数的长度加上 1,所以需要再定义一个 g[i] 状态数组来表示,也就是 g[i - 1] + 1,但是如果之前找不到一个以 i - 1 为结尾的数组,那么 g[i - 1] 就是 0,此时就不能继续加 1,因为 num[i] 是负数,这个长度不能加
为了简便,长度为 1 时的状态可以和下面长度大于 1 的合并一下,不影响结果
接下来看 g[i] 的状态转移方程:同理,也可以分为长度为 1 和长度大于 1 两种情况,接着二者又可以分为 num[i] 大于 0 和小于 0 两种情况,当 num[i] 大于 0 时,需要找到 i - 1 为结尾的乘积为负数的最长长度,也就是 g[i - 1],然后加 1,这里还是一样的,如果没有找到,那么 g[i - 1] 就是 0,num[i] 为正数,要求的是负数,所以这个 1 需要判断一下才能加,num[i] 小于 0 时,就需要找一个 i - 1 为结尾的乘积为正数的最长长度,也就是 f[i - 1] 再加 1,这时就不需要判断,找不到也没关系,可以直接 + 1
长度为 1 时也可以合并一下,不影响结果
nums[i] 等于 0 的情况直接不考虑就行
初始化:如果 nums[0] 是大于 0 的话,g[1] 应该是 0,也就是 g[0] = 0即可, 如果是小于 0 的话 g[1] 应该是 1,也就是 f[0] 应该是 0
填表顺序:从左到右,两个表一起填
返回值:f 表中的最大值
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(f[i],ret); } return ret; } }
5. 等差数列划分
状态表示:以 i 位置为结尾时的等差数列的个数
状态转移方程:由于至少需要三个元素才符合题目中等差数列的要求,所以需要判断 i - 2,i - 1,i 三个元素,当这三个元素符合等差数列时,那么以 i - 1 为结尾的等差数列再加上 i 也是等差数列,等差数列的个数就 + 1,如果说这三个元素不符合等差数列,那么以 i 为结尾的等差数列个数就是 0
初始化:由于三个元素才能进行等差数列的判断,所以 dp[0],dp[1] 初始化为 0
返回值:如果数组长度小于 3 直接返回 0,大于等于 3 就返回 dp 数组的和
class Solution { public int numberOfArithmeticSlices(int[] nums) { int n = nums.length; int[] dp = new int[n]; int ret = 0; if(n < 3) return 0; for(int i = 2;i < n;i++){ dp[i] = (nums[i] - nums[i - 1]) == (nums[i - 1] - nums[i - 2]) ? dp[i - 1] + 1:0; ret += dp[i]; } return ret; } }
6. 最长湍流子数组
状态表示:先用 dp[i] 来表示以第 i 个位置为结尾时的最长湍流数组的长度
f[i]:表示以第 i 个位置为结尾时表示上升状态的最长湍流数组的长度
f[i]:表示以第 i 个位置为结尾时表示下降状态的最长湍流数组的长度
状态转移方程:
第 i - 1 和 i 位置的状态可能会有下降,上升,相等三种状态,所以定义一个 dp 状态就不够了,需要定义一个上升状态和一个下降状态,当 i - 1 到 i 处于下降状态时,之前应该是处于上升状态的,也就是 f[i - 1],再加上 1 就是以第 i 个位置为结尾时处于下降状态的最长数组长度,上升也是一样的道理,需要在第 i - 1 位置处于下降状态,就是 g[i - 1] + 1,相等时等于 1 即可
初始化:由于 1 个元素也可以称为湍急子数组,所以可以把 0 下标初始化为 1,又因为状态转移方程中的其他情况是 1 ,为了方便,可以把初始的两个 dp 表都初始化为 1
填表顺序:从左到右
返回值:下降和上升状态的最大值
class Solution { public int maxTurbulenceSize(int[] arr) { int n = arr.length; int[] f = new int[n]; int[] g = new int[n]; for(int i = 0;i < n;i++){ f[i] = g[i] = 1; } int ret = 1; for(int i = 1;i < n;i++){ if(arr[i] > arr[i - 1]){ g[i] = f[i - 1] + 1; }else if(arr[i] < arr[i - 1]){ f[i] = g[i - 1] + 1; } ret = Math.max(Math.max(ret,g[i]),f[i]); } return ret; } }
7. 单词拆分
状态表示:dp[i] 表示以 i 为结尾时,区间 [0 , i] 之间内能否被字典中的单词拼接而成
状态转移方程:
可以把区间分为两段,设 j 为最后一个单词的起始位置的下标,如果 [0 , j - 1] 区间内能够被字典中的单词拼接而成,也就是 dp[j - 1],再加上 j ~ i 区间的单词在数组中,那么就说明 0 ~ i 区间可以被字典中的单词拼接而成
初始化:为了方便表示 ,dp 数组还是开 n + 1(n 为所给字符串的长度),此时 dp[0] 需要设置为 true 才能不影响后续的判断,如果是 false 的话,那么后面区间就一直都不可以被拼接,dp 数组长度 + 1 之后,为了更方便的表示下标的映射关系,可以把原来的字符串 s 最前面加一个长度为 1 的占位符,这样字符串的下标也对应着 dp 表的下标
填表顺序:从左到右
返回值:dp[n]
为了便于查找 j ~ i 的字符串是否在字典中,可以把题中的字典映射到哈希表中
class Solution { public boolean wordBreak(String s, List<String> wordDict) { int n = s.length(); boolean[] dp = new boolean[n + 1]; dp[0] = true; s = " " + s; Set<String> hash = new HashSet(wordDict); for(int i = 1;i <= n;i++){ //字符串长度 + 1,对应的 j 最小就是 1 下标 for(int j = i;j >= 1;j--){ //substring 前闭后开 ,所以 i + 1 if(dp[j - 1] && hash.contains(s.substring(j,i + 1))){ dp[i] = true; //如果找到一种再往前就不用找了 break; } } } return dp[n]; } }
8. 环绕字符串中唯一的子字符串
状态表示:dp[i] 表示以 i 位置为结尾时,有多少子串出现
状态转移方程:
和上一题其实差不多,可以分为长度为 1 和长度大于 1 的,只需要判断是否是连续的,前一个是“z”后一个是 "a" 也算是连续的
初始化:由于长度为 1 时可以算出现一次,长度大于 1 就是找到以 i - 1 为结尾的子串再加上 s[i] ,整体的数量还是 dp[i - 1],dp[i] 就是把长度为 1 和长度大于 1 的两种情况加起来,所以可以把整个 dp 表初始化为 1 ,然后就只需要判断长度大于 1 时的情况直接相加就行
填表顺序:从左到右
返回值:由于 dp[i] 中存储的是以 i 为结尾时的子串出现的次数,这就可能出现多次,例如“cac”
相同的子串只能统计一次,并且可以发现,以同一个字符结尾的子串只需要统计最长的即可,短的情况就包含在了长的情况,所以可以额外定义一个 hash 表来存储最终的答案,最后只需返回 hash 表中的所有和即可
class Solution { public int findSubstringInWraproundString(String s) { int n = s.length(); int[] dp = new int[n]; Arrays.fill(dp, 1); //表示 26 个字母 int[] hash = new int[26]; char[] chars = s.toCharArray(); for(int i = 1;i < n;i++){ if((chars[i] == (chars[i - 1] + 1)) || (chars[i] == 'a'&&chars[i - 1] == 'z')){ dp[i] += dp[i - 1]; } } int ret = 0; for(int i = 0;i < n;i++){ //更新为以当前字符为结尾最长子串的数量 hash[chars[i] - 'a'] = Math.max(hash[chars[i] - 'a'],dp[i]); } for(int x : hash) ret += x; return ret; } }