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

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param nums int整型一维数组
     * @return int整型
     */
    public int maxSubArrayLengthTwo (int[] nums) {
        // write code here

        if(nums.length ==1){
            return 1;
        }

        // 假设不允许断开的情况下，0-i 最大连续长度
        int[] leftMaxSeq = new int[nums.length];
        Arrays.fill(leftMaxSeq, 1);
        for (int i = 0 ; i < leftMaxSeq.length-1 ; i++) {
            if (nums[i]  <  nums[i + 1]) {
                leftMaxSeq[i + 1] = leftMaxSeq[i]+1;
            }
        }

        // 假设不允许断开的情况下，i-max 最大字串连续长度
        int[] rightMaxSeq = new int[nums.length];
        Arrays.fill(rightMaxSeq, 1);
        for (int i = rightMaxSeq.length -1 ; i-1 > 0  ; i--) {
            if (nums[i-1]  <  nums[i]) {
                rightMaxSeq[i-1] =rightMaxSeq[i]+1;
            }
        }

        int max = 1;
        for(int i=0;i< nums.length ;i++){
            max = Math.max(max,leftMaxSeq[i]);
        }

        // 0-i 的最大长度 --> i 到 max 的最大长度等于当前最大长度
        for(int i=0;i< nums.length ;i++){

            if(i == 0){
              //  System.out.print(rightMaxSeq[0]+","+i);
                int temp = rightMaxSeq[1];
                if(nums[1]  >= 2  && nums[0] >=  nums[1]){ // 说明可修正
                    temp++;
                }

                max = Math.max(max,temp);
                continue;
            }

            if(i == nums.length -1){
                int temp = leftMaxSeq[nums.length-2];
              //  System.out.print(rightMaxSeq[0]+","+i);
                if(nums[nums.length-1]  <= nums[nums.length-2]   ){ // 说明可修正
                    temp++;
                }
                max = Math.max(max,temp);
                continue;
            }

            if(nums[i+1] > nums[i-1] +1){ // 有修正空间
                max = Math.max(max,leftMaxSeq[i-1]+rightMaxSeq[i+1]+1);
            }
            else { // 只有单边修正空间
                int right = rightMaxSeq[i+1] ;
                if(nums[i+1]>=2){ // 考虑向后最大字串，修改前面一个字符
                    right ++;
                }
                //System.out.print(leftMaxSeq[i-1]+","+i);
                int temp = Math.max(leftMaxSeq[i-1]+1,right);
                max = Math.max(max,temp);
            }
        }

        return max;


    }
}