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

时间复杂度O(n),空间复杂度O(n)

[C++ 代码]

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型
     */
    int maxSubArrayLengthTwo(vector<int>& nums) {
        int n = nums.size();
        // 1. 分别计算以当前元素为结尾和为开始的最长严格上升子数组
        vector<int> end(n);
        vector<int> start(n);
        end[0] = 1;
        for(int i=1; i<n; ++i)  end[i] = (nums[i]>nums[i-1] ? end[i-1]+1 : 1);
        start[n-1] = 1;
        for(int i=n-2; i>=0; --i)   start[i] = (nums[i]<nums[i+1] ? start[i+1]+1 : 1);

        int res = 1;
        for(int i=0; i<n; ++i){
            // 如果非首尾元素且满足前一个元素比后一个元素至少小2，说明可以改变当前元素承上启下
            if(i>0 && i<(n-1) && nums[i-1]+1 < nums[i+1])   res = max(res, 1+end[i-1]+start[i+1]);       
            else{
                // 启下：元素不能是最后一个，且后一个元素不能是最小值
                if(i<(n-1) && nums[i+1]>1) res = max(res, 1+start[i+1]);
                // 承上：元素不能是第一个，且前一个元素不能是最大值
                if(i>0 && nums[i-1]<1e5)   res = max(res, 1+end[i-1]);
            }
        }
        return res;
    }
};