
mzoe666888
2022/06/04阅读:15主题:兰青
内卷大厂系列《动态规划-子数组模型》
《动态规划-子数组模型》,您将学到子数组模型的本质是什么,子数组问题想到以什么什么结尾,因为不管什么子数组,一定是以某个数结尾的。
一、题目
给定一个数组arr,长度为n,最多可以删除一个连续子数组,求剩下的数组必须是严格连续递增的子数组最大长度。
二、分析
首选一说子数组,必定是连续的,其次题目要求是最多删除一个连续子数组,而且删完后,剩下的数组还必须是严格递增的子数组,求最大长度是多少
允许最多删一个,也可以不删除,本身原始数组就是严格的连续递增子数组
删只需要删连续子数组,不要求删连续递增子数组

当看到子数组问题,必定想到以什么什么结尾模型,因为任何子数组一定以某个数结尾,假设当前来到子数组来到i位置,左边可以不删,也可以删,那么当前i位置的最大长度是多少,依次类推以0位置结尾求出最大长度,以1位置求出最大长度,以i位置结尾求出最大长度,每次答案在max下就是最终答案
dp[i]
含义:必须以i位置结尾,左边可以删,也可以不删的情况下,最长递增子数组最大长度是多少
dp[i-1]
含义:必须以i-1位置结尾,左边可以删,也可以不删的情况下,最长递增子数组最大长度是多少
以i位置结尾,罗列可能性:
-
可能性一:要i-1且arr[i-1] < arr[i], dp[i] = dp[i-1] + 1
-
可能性二:不用i-1,删除i-1,最多能删除一次,那必须要求i左边比i小的所有数冲到最大的长度是不允许有删除操作的,如果删除操作,必定不满足题意规定。
以i位置结尾的情况下,存在两种可能性,每个位置分析出两种可能性,分别是dp[i]和dp[i']
dp[i]代表以i位置结尾的情况下,左边可以不删
dp[i']代表以i位置结尾的情况下,左边发生删除,且左边所有比i'小的数冲到最大长度且他们的左边不能有删除操作
三、实现
暴力方法
public static int maxLen1(int[] arr) {
int ans = max(arr);
int n = arr.length;
for (int L = 0; L < n; L++) {
for (int R = L; R < n; R++) {
int[] cur = delete(arr, L, R);
ans = Math.max(ans, max(cur));
}
}
return ans;
}
public static int[] delete(int[] arr, int L, int R) {
int n = arr.length;
int[] ans = new int[n - (R - L + 1)];
int index = 0;
for (int i = 0; i < L; i++) {
ans[index++] = arr[i];
}
for (int i = R + 1; i < n; i++) {
ans[index++] = arr[i];
}
return ans;
}
public static int max(int[] arr) {
if (arr.length == 0) {
return 0;
}
int ans = 1;
int cur = 1;
for (int i = 1; i < arr.length; i++) {
if (arr[i] > arr[i - 1]) {
cur++;
} else {
cur = 1;
}
ans = Math.max(ans, cur);
}
return ans;
}
动态规划中罗列可能性二有些难!
四、总结
子数组问题:以什么什么开头,以什么什么结尾怎么怎么样,求出所有开头或结尾,那么答案必在其中,这种模型技巧很好用
看到子串和子数组,想什么?以什么什么开头 或 以什么什么结尾 来分析,每个位置开头的情况下,答案是什么,或 每个位置结尾的情况下,答案是什么,答案必在其中
作者介绍
