《动态规划-子数组模型》，您将学到子数组模型的本质是什么，子数组问题想到以什么什么结尾，因为不管什么子数组，一定是以某个数结尾的。

一、题目

给定一个数组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;
}

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

四、总结

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

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