算法

(DP) $O(n)$

一、 确定状态

• 最后一步：对于最优的策略，一定有最优的元素a[j]
• 第一种情况：最优策略中最长连续上升子序列就是{a[j]}，答案是1
• 第二种情况：子序列长度大于1，那么a[j]前一个元素肯定是a[j-1].这种情况一定是a[j-1] < a[j]
• 因为是最优策略，所以它选中的以a[j-1]结尾的连续上升子序列一定是最长的

子问题

• 要求以a[j-1]结尾的最长连续上升子序列
• 本来是求以a[j]结尾的最长连续上升子序列
• 化为子问题
• 状态：以f[j]$=$以a[j]结尾的最长连续上升子序列的长度

二、 转移方程

三、 初始条件和边界情况

• 情况2必须满足：
  – j > 0，即a[j]前面至少还有一个元素
  – a[j] > a[j-1]，满足单调性

• 初始条件：空

四、计算顺序

• 以f[j]$=$以a[j]结尾的最长连续上升子序列的长度
• 计算f[0], f[1], f[2], ..., f[n-1]
• 因为我们不知道最优策略中最后一个元素是哪一个a[j]，所以答案是max{f[0], f[1], f[2], ..., f[n-1]}

Java 代码

class Solution {

    public int LIS(int[] a, int n) {
        int[] f = new int[n];
        int res = 0;
        for (int i = 0; i < n; ++i) {
            // case 1
            f[i] = 1;

            // case 2
            if (i > 0 && a[i] > a[i - 1]) {
                f[i] = f[i - 1] + 1;
            }

            res = Math.max(res, f[i]);
        }

        return res;
    }

    public int findLengthOfLCIS(int[] A) {
        int n = A.length;
        if (n == 0) return 0;

        return LIS(A, n);
    }
}