version at: 2022-03-29

/**
1. dp 如果以i分割, nums[i] 可以连到前面某个子序列上扩展成为新的子序列, 所有能用DP
2. dp
    2.1 状态定义: f[i] 以i结尾的子序列的长度的最大值
    2.2 状态计算: 以i划分
        2.2.1 包含i的子序列: f[i] = 1 + MAX(f[0]...f[j]...f[i-1]) 仅当nums[i] > nums[j]时 
        2.2.2 i单独为子序列: f[i] = 1
    2.3 f[~] 初始状态是1, 返回 MAXf[~]
*/
class Solution {
    public int lengthOfLIS(int[] nums) {
        int[] f = new int[nums.length+1];

        Arrays.fill(f, 1);

        for (int i = 2 ; i <= nums.length ; i++) {
            for (int j = 1; j < i; j++) {
                if (nums[i-1] > nums[j-1]) {
                    f[i] = Math.max(f[i], 1+f[j]);
                }
            }
        }

        return Arrays.stream(f).max().getAsInt();
    }
}

version at: 2020-01-26

/**
1. 每个值可以接到前面任意一个子序列后面构成递增子序列, 所以可以用动态规划来做
2. 状态定义: f[i] 是 以i结尾的最长上升子序列长度
3. 状态计算: f[i] = if (a[i] > a[k]) f[i] = max(a[k] + 1) 0 <= k < i
4. 边界: f[~] = 1
*/

class Solution {
    public int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int n = nums.length;
        int[] f = new int[n];
        Arrays.fill(f, 1);
        for (int i = 0; i < n ; i++)
            for (int j = 0; j < i; j ++)
                f[i] = Math.max(f[i], nums[i] > nums[j] ? f[j] + 1 : 1);

        return Arrays.stream(f).max().getAsInt();
    }
}