300. 最长递增子序列

中等

题目描述

解法：动态规划，dp[i] 表示截止到为止 i 的最长递增子序列，状态转移方程：dp[i] = Math.max(dp[j] + 1, dp[i]);

class Solution {
    public int lengthOfLIS(int[] nums) {
		int res = Integer.MIN_VALUE;
		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[j] + 1, dp[i]);
				}
			}
			res = Math.max(res, dp[i]);
		}
		return res;
    }
}