最长上升子序列

最长上升子序列

题目：
给定一个无序的整数数组，找到其中最长上升子序列的长度。

示例:

输入: [10,9,2,5,3,7,101,18]
输出: 4
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。

class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        if(n == 0)
            return 0;
        
        //数组定义：dp[i]表示0 -> i-1的最长上升子序列的长度
        int dp[] = new int[n + 1];
        
		//初始化
        dp[0] = 0;
        dp[1] = 1;
        int ans = 1;
        
        /**
        状态方程：dp[i] = max(dp[i], dp[j] + 1)
        **/
        for(int i = 2; i <= n; i++) {
            dp[i] = 1;
            
            for(int j = 0; j < i - 1; j++) {
                if(nums[j] < nums[i - 1]) {
                    dp[i] = Math.max(dp[i], dp[j + 1] + 1);
                }
            }
            
            ans = Math.max(ans, dp[i]);
        }
        
        return ans;
    }
}