Longest Increasing Subsequence

Given a sequence of integers, find the longest increasing subsequence (LIS).

You code should return the length of the LIS.

Example
For [5, 4, 1, 2, 3], the LIS is [1, 2, 3], return 3
For [4, 2, 4, 5, 3, 7], the LIS is [4, 4, 5, 7], return 4

分析

由于是求最长的子序列，可以index不连续，可以考虑用DP解决。比如dp[i]表示以为i元素结尾的子序列的最大长度，那么可以根据所有dp[j](j < i)来得到dp[i]的值。

复杂度

time: O(n^2), space: O(n)

代码

public class Solution {    public int longestIncreasingSubsequence(int[] nums) {        if (nums.length == 0)return 0;        int max = 0;        int[] dp = new int[nums.length];        for (int i = 0; i < nums.length; i++) {dp[i] = 1;for (int j = 0; j < i; j++) {    if (nums[i] >= nums[j]) // 必须是递增        dp[i] = Math.max(dp[i], dp[j] + 1);}max = Math.max(max, dp[i]); // 更新全局最大值        }        return max;    }}