题目描述

给定一个长度为n的正整数数组nums，可以任意改变数组的其中一个元素，原来的和改变的元素范围都在[1,100000]之内，然后返回nums的最长"严格上升"子数组的长度。

1.子数组是连续的，比如[1,3,5,7,9]的子数组有[1,3]，[3,5,7]等等，但是[1,3,7]不是子数组。

2.严格上升指在数组上任意位置都满足 nums[i] < nums[i+1]，比如[1,2,2,3]，其中[1,2,2]不是严格上升的子数组，[1,2]则是的。

数据范围： 1≤n≤10^5， 1≤num[i]≤10^5

要求： 空间复杂度 O(n)，时间复杂度 O(n)

解题思路：贪心

假设nums[k]改变元素值可以让严格上升的子数组长度最大，那么nums[k]改变后的值必然在nums[k-1]和nums[k+1]之间。注意边界条件，当k = 0 或k = n-1时要另外讨论。

根据贪心的思路，我们遍历nums数组的每个元素位置k。k - 1开始往前找，k + 1开始往后找，直到不符合严格上升的条件为止，得到最长严格上升子数组的长度。

时间复杂度O(n^2)。

优化时间复杂度：动态规划

维护两个数组ed和st。

ed[i]表示以元素位置i为结尾的最长严格上升子数组的长度；st[i]表示以元素位置i为开头的严格上升子数组长度。

容易得到状态转移方程

ed[i] = nums[i] > nums[i - 1] ? ed[i - 1] + 1 : 1

st[i] = nums[i] < nums[i + 1] ? st[i + 1] + 1 : 1

接下来再按照贪心的思路，遍历nums数组的每个元素位置k。如果 nums[k - 1] + 1 < nums[k + 1]，即nums[k]的相邻两个元素相差超过2，那么修改nums[k]的值可以得到一个贪心答案 ans = 1 + ed[i - 1] + st[i + 1]。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型
     */
    int maxSubArrayLengthTwo(vector<int>& nums) {
        int n = nums.size();
        if(n == 1) return 1;
        vector<int> ed(n, 1), st(n, 1);
        int ans = 1;
        for(int i = 1; i < n; ++i) {
            if(nums[i] > nums[i - 1]) {
                ed[i] = ed[i - 1] + 1;
            }
            if(nums[i - 1] < 10000) {
                ans = max(ans, ed[i - 1] + 1);
            }
        }
        for(int i = n - 2; i >= 0; --i) {
            if(nums[i] < nums[i + 1]) st[i] = st[i + 1] + 1;
            if(nums[i + 1] > 1) {
                ans = max(ans, st[i + 1] + 1);
            }
        }
        for(int i = n - 2; i >= 1; --i) {
            if(nums[i - 1] + 1 < nums[i + 1]) {
                ans = max(ans, 1 + ed[i - 1] + st[i + 1]);
            }
        }
        return ans;
    }
};