674. Longest Continuous Increasing Subsequence

LeetCode

设f[i]为：以a[i]结尾的最长连续上升子序列的长度。因为子序列是“最长无重复子序列”，所以以a[i]结尾的最长连续上升子序列的倒数第二个元素必然是a[i - 1]，否则就违背了**“连续”**。既然以a[i]结尾的最长连续上升子序列是**最长**的，那么如果它被减去a[i]这个元素的长度，必然是第二长的。

所以长度f[i]可以被分解为两部分（其中一部分是规模更小的有相同结构的子问题）：

  • a[i]这个元素本身的长度
  • 以a[i - 1]结尾的最长连续子序列的长度

状态转移方程：

  • f[i] = max{ f[i - 1] + 1 } （如果 a[i - 1] < a[i]）
  • f[i] = 1（如果 a[i - 1] >= a[i]），因为只有符合这种条件的i才是连续上升子序列的起点

初始条件：f[0] = 1

class Solution {
    public int findLengthOfLCIS(int[] nums) {
        if (nums.length() <= 1) {
            return nums.length();
        }
        int f[] = new int[nums.length()];
        f[0] = 1;
        int largest = f[0];
        for (int i = 1; i < nums.length(); i++) {
            if (nums[i - 1] < nums[i]) {
                f[i] = f[i - 1] + 1;
            } else {
                f[i] = 1;
            }
            largest = Math.max(largest, f[i]);
        }
        return largest;
    }
}