题解 | JAVA O(1)空间 #最长严格上升子数组(一)# [P2]

首先比较容易会想到需要在dp时每一位考虑用了wildcard和没用wildcard的情况

没用wildcare的情况比较简单(见F(i)定义)

用了wildcare的情况为什么要考虑 G(i) 和 H(i)，请看以下案例：
10, 3, 10, 5, 6
G(2)的最优解是[1, 3, 10], i.e. 把第一个10换成1
H(2)的最优解时[3, 4], i.e. 把第二个10换成4
虽然此刻G(2)的长度大于H(2), 但是最终解选择的是H(2), i.e. [3, 4, 5, 6]

反之，如果案例变成
10，3，10，11，12
最终解在选择的是G(2), i.e. [1, 3, 10, 11, 12]

总之最终解需要考虑每一位G和H两种情况。
然后把dp公式写出来发现对于i, 计算F(i)/G(i)/H(i)只需要知道F(i-1)/G(i-1)/H(i-1)
那么dp只需要记忆上一轮的值

时间 O(n): 每个数只visit一遍
空间 O(1): 只需要记忆上一轮的F/G/H和global max的F/G/H

import java.util.*;

public class Solution {
    public int maxSubArrayLengthTwo (int[] nums) {
      
      // dp定义：
      // F(i): MSALength ending at nums[i], and haven't used the wildcard.
      //   = (nums[i] > nums[i-1]) ? F(i-1) + 1 : 1
      // 最简单的情况，没有用wildcard
      // 
      // G(i): MSALength ending at nums[i], and the wildcard on some j < i
      //   = MAX of {
      //     optionA: nums[i] > nums[i-1] ? G(i-1）+ 1 : 1
      //     optionB: nums[i] > vH[i-1] ? H(i-1) + 1 : 1
      //   }
      // G(i)的情况是已经replace了之前的某个数，那么需要参考G(i-1)和H(i-1)
      // 
      // H(i): MSALength ending at nums[i], and wildcard is used on nums[i]
      //   = F(i-1) + 1
      // vH(i): optimal wildcard to replace nums[i]
      //   = nums[i-1] + 1

      if (nums.length <= 1) return nums.length;
      // 初始： MSA = { nums[0] }
      int fMax = 1, gMax = 1, hMax = 1; // global max
      int f = 1, g = 1, h = 1;  // previous f/g/h
      int vh = 1;  // use smallest possible wildcard
      
      for (int i = 1; i < nums.length; i++) {
        int f_cur = (nums[i] > nums[i-1]) ? f + 1 : 1;
        int g_curA = (nums[i] > nums[i-1]) ? g + 1 : 1;
        int g_curB = (nums[i] > vh) ? h + 1 : 1;
        int g_cur = Math.max(g_curA, g_curB);
        int h_cur = f + 1;
        
        // done using previous f, update prev to cur
        f = f_cur;
        g = g_cur;
        h = h_cur;
        vh = nums[i-1] + 1;
        
        fMax = Math.max(fMax, f);  // 其实fMax都不用记，写出来看的舒服
        gMax = Math.max(gMax, g);
        hMax = Math.max(hMax, h);
      }
      
      return Math.max(gMax, hMax);  // 最优解一定在用wildcard的两种情况中
    }
}