300. Longest Increasing Subsequence

Input: [10,9,2,5,3,7,101,18]
Output: 4 
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

思路：

• 创建大小和输入数组一样的数组memo，记录当前最大的上升序列长度，初始值为1
• 设i为后面的数字，j为i前面的所有数字，memo中记录memo[j] + 1和memo[i]的最大值，因为memo[i]中的值是实时刷新的，所以需要进行比较来维护当前的最大值。以[10,22,9,33]为例，正确答案是memo[3]为3，如果没有进行比较，只是让memo[i] = memo[j] + 1的话，memo[3]就为2，这是错的答案
• 临时变量max记录当前最大值

public int lengthOfLIS(int[] nums) {
    if (nums == null || nums.length == 0) return 0;
    int[] memo = new int[nums.length];
    Arrays.fill(memo, 1);
    int max = 1;
    for (int i = 1; i < nums.length; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {
                memo[i] = Math.max(memo[i], memo[j] + 1);
                max = Math.max(max, memo[i]);
            }
        }
    }
    return max;
}