题解 | #最长严格上升子数组(一)#

public class Solution {

/**
 * 用left[i]表示以nums[i]结尾的最长严格上升子数组   用right[i]表示以nums[i]开始的最长严格上升子序列
 * @param nums
 * @return
 */
public static int maxSubArrayLengthTwo(int[] nums){
    int n = nums.length;
    if (n <= 2){//当n <= 2返回数组长度即可
        return n;
    }
    int res = 1;
    int[] left = new int[n];//left[i]表示以nums[i]结尾的最长严格上升子数组长度
    for (int i = 0; i < n; i++){
        left[i] = 1;
        if (i > 0 && nums[i] > nums[i - 1]){
            left[i] = left[i - 1] + 1;
            res = Math.max(res, left[i]);
        }
    }
    if (res == n){//如果res == n即该数组就是严格上升数组，直接返回res即可
        return res;
    }
    int[] right = new int[n];//right[i]表示以nums[i]开头的最长严格上升子数组长度
    for (int i = n - 1; i >= 0; i--){
        right[i] = 1;
        if (i < n - 1 && nums[i] < nums[i + 1]){
            right[i] = right[i + 1] + 1;
        }
    }

    for (int i = 0; i < n; i++){
        if (i == 0){//i == 0是特殊情况
            if (right[i] == 1 && nums[i + 1] > 1){// right[i] == 1说明以nums[0]为起点的严格上升子数组长度为1 举例[3, 2, 4]
                //所以此处将3调整为1 长度更新为right[i + 1] + 1 但要注意nums[i + 1] 即nums[2] > 1因为这是一个正数数组，如果nums[2] = 1 此处将不能进行调整
                res = Math.max(res, right[i + 1] + 1);
            }
        }else if (i == n - 1){//i == n - 1是另一种特殊情况
            if (left[i] == 1){//left[i] == 1说明以nums[n - 1]为终点的严格上升子数组长度为1 举例{3, 4, 2}
                //只要将nums[i]调整成大于nums[i - 1]的数即可 长度更新为left[i - 1] + 1
                res = Math.max(res, left[i - 1] + 1);
            }
        }else {//其他情况
            if (right[i] == 1){//如果right[i] == 1即以nums[i]为起点的严格上升子数组长度为1，举例{3, 4, 9, 8, 10} 此时nums[i] = 9
                if (nums[i + 1] - nums[i - 1] >= 2) {//如果nums[i + 1] - nums[i - 1] >= 2说明nums[i]有调整的空间可以进行调整，调整之后的长度更新为left[i] + right[i + 1]
                    res = Math.max(res, left[i] + right[i + 1]);
                }else {//如果不满足nums[i + 1] - nums[i - 1]即说明不能将这两段连起来 举例{3, 4, 9, 5, 10} 此时nums[i] = 9
                    if (nums[i + 1] > 1){//如果nums[i + 1] > 1还可以进行后部分子数组的调整 更新长度为 right[i + 1] + 1 如果nums[i + 1] == 1则无法进行调整
                        res = Math.max(res, right[i + 1] + 1);
                    }
                }
            }
            if (left[i] == 1){//如果left[i] == 1即以nums[i]为终点的严格上升子数组长度为1，举例{3， 4， 9， 8， 12}，此时nums[i] = 8
                if (nums[i + 1] - nums[i - 1] >= 2) {//如果nums[i] + 1 - nums[i - 1] >= 2 说明nums[i]有调整的空间 调整之后的长度更新为right[i] + left[i - 1]
                    res = Math.max(res, right[i] + left[i - 1]);
                }else {//如果不满足 可以调整前部分子数组，更新长度为Left[i - 1] + 1
                    res = Math.max(res, left[i - 1] + 1);
                }
            }
        }

    }
    return res;
}

}