最长严格上升子数组(一)

1. 构建两个dp数组dpLeft和dpRight，其中的元素表示分别以数组中某个数结尾和开头的最长递增子数组长度，可以直接用O(n)时间复杂度的动态规划把这两个数组求出来。
2. 然后遍历数组，检查是否可以通过修改nums[i]将左右两边的最长递增子数组连起来。如果不能连起来，就看nums[i]是修改完成为左边递增子数组的结尾能使递增子数组更长，还是修改完成为右边递增子数组的开头能使递增子数组更长。

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @return int整型
     */
    public int maxSubArrayLengthTwo (int[] nums) {
        // 预处理
        int n = nums.length;
        if(n == 1) return 1;
        int[] dpLeft = new int[n];     // dpLeft[i]表示以nums[i]结尾的最长递增子数组长度
        dpLeft[0] = 1;
        for(int i = 1; i < n; i++){
            dpLeft[i] = nums[i] > nums[i - 1]? dpLeft[i - 1] + 1: 1;
        }
        int[] dpRight = new int[n];     // dpRight[i]表示以nums[i]开头的最长递增子数组长度
        dpRight[n - 1] = 1;
        for(int i = n - 2; i >= 0; i--){
            dpRight[i] = nums[i] < nums[i + 1]? dpRight[i + 1] + 1: 1;
        }
        int maxLen = 1;
        for(int i = 0; i < n; i++){
            if(0 < i && i < n - 1 && nums[i + 1] - nums[i - 1] > 1){
                // 左右两边的递增子数组可以接起来
                maxLen = Math.max(maxLen, dpLeft[i - 1] + dpRight[i + 1] + 1);
            }else{
                // 两边接不起来就看nums[i]接前面更长还是接后面更长
                if(i > 0){
                    maxLen = Math.max(maxLen, dpLeft[i - 1] + 1);
                }
                if(i < n - 1 && nums[i + 1] > 1){
                    // 由于是正数数组，后一个数比1大才有可能接起来
                    maxLen = Math.max(maxLen, dpRight[i + 1] + 1);
                }
            }
        }
        return maxLen;
    }
}

 复杂度分析

public static int maxSubArrayLengthTwo(int[] nums) {
        // write code here
        if (nums.length <= 1) return nums.length;

        int tmp1 = nums[0], tmp2 = nums[0];

        for (int num : nums) {
            if (num != tmp1) {
                tmp2 = num;
                break;
            }
        }
        if (tmp1 == tmp2) return 2;

        int coordinator = 0;
        int[] deCreArr = new int[nums.length];
        Arrays.fill(deCreArr, nums.length - 1);
        for (int i = 0; i < nums.length - 2; i++) {
            if (nums[i + 1] <= nums[i] && (
                    (i == 0 && nums[1] > 1) ||
                            (i > 0 && i < nums.length - 1 && nums[i + 2] - nums[i] > 1)
            )) deCreArr[coordinator++] = i + 1;
        }

        if (nums.length > 3 && nums[nums.length - 2] <= nums[nums.length - 3] && nums[nums.length - 2] - nums[nums.length - 4] > 1)
            deCreArr[coordinator] = nums.length - 2;
        int res = 0;
        // 只有一个递减 TODO: BUG -> 无法确认全局是否仅有一个乱序元素
        if (deCreArr[0] == deCreArr.length - 1 || deCreArr[1] == deCreArr.length - 1) {
            int distCnt = nums.length;
            for (int i = 0; i < nums.length - 2; i++)
                if ((i == 0 && nums[0] == nums[1] && nums[0] == 1)
                        || (i > 0 && nums[i] == nums[i + 1] && nums[i] - nums[i - 1] == 1))
                    distCnt--;
            res = distCnt;
        } else
            // 多个递减
            for (int i = 0; i < deCreArr.length - 2; i++)
                res = Math.max(res, deCreArr[i + 2] - deCreArr[i] + 1);
        return res;
    }

public int maxSubArrayLengthTwo (int[] nums) {
        // write code here
        int n = nums.length;
        int[] dpPre = new int[n];
        dpPre[0] = 1;
        int[] dpSuf = new int[n];
        dpSuf[n - 1] = 1;
        for (int i = 1; i < n; i++) {
            dpPre[i] = nums[i] > nums[i - 1] ? dpPre[i - 1] + 1 : 1;
        }
        for (int i = n - 2; i >= 0; i--) {
            dpSuf[i] = nums[i] < nums[i + 1] ? dpSuf[i + 1] + 1 : 1;
        }
        int res = 1, curMax = 1;
        for (int i = 0; i < n; i++) {
            if (i > 0 && i < n - 1 && nums[i - 1] + 1 < nums[i + 1]) {
                curMax = dpPre[i - 1] + dpSuf[i + 1] + 1;
            } else {
                if (i > 0)
                    curMax = Math.max(dpPre[i], dpPre[i - 1] + 1);

                if (i < n - 1 && nums[i + 1] > 1)
                    curMax = Math.max(Math.max(curMax, dpSuf[i]), dpSuf[i + 1] + 1);
            }
            res = Math.max(res, curMax);
        }
        return res;
    }