mzoe666888

V1

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;
}

动态规划中罗列可能性二有些难!

四、总结

子数组问题:以什么什么开头,以什么什么结尾怎么怎么样,求出所有开头或结尾,那么答案必在其中,这种模型技巧很好用

看到子串和子数组,想什么?以什么什么开头以什么什么结尾 来分析,每个位置开头的情况下,答案是什么,或 每个位置结尾的情况下,答案是什么,答案必在其中

分类:

后端

标签:

数据结构与算法

作者介绍

mzoe666888
V1