[Vssue]0300.最长上升子序列.md

if(nums.length <= 1) return nums.length;
int[] dp = new int[nums.length];
Arrays.fill(dp,1);

int result = 1;
for(int i = 1; i < nums.length; i++){
    for(int j = 0; j < i; j++){
        if(nums[j] < nums[i]){
            dp[i] = Math.max(dp[i], dp[j] + 1);
        }
    }
    if(dp[i] > result) result = dp[i];
}
return result;

// 例: nums = [0,1,0,3,2], 面试高频题.
i = 1: nums[1] = 1, dp = [1,1,1,1,1], result = 0
    j = 0: nums[0] = 0, dp[1] = max(1,1+1) = 2 (子序列 [0,1])
i = 2: nums[2] = 0, dp = [1,2,1,1,1], result = 2
    j = 0: nums[0] = 0, 继续遍历 (不满足递增)
    j = 1: nums[1] = 1, 继续遍历 (不满足递增)
i = 3: nums[3] = 3, dp = [1,2,1,1,1], result = 2
    j = 0: nums[0] = 0, dp[3] = max(1,1+1) = 2 (子序列 [0,3])
    j = 1: nums[1] = 1, dp[3] = max(2,2+1) = 3 (子序列 [0,1,3])
    j = 2: nums[2] = 0, dp[3] = max(3,1+1) = 3 (子序列 [0,1,3])
i = 4: nums[4] = 2, dp = [1,2,1,3,1], result = 3
    j = 0: nums[0] = 0, dp[4] = max(1,1+1) = 2 (子序列 [0,2])
    j = 1: nums[1] = 1, dp[4] = max(2,2+1) = 3 (子序列 [0,1,2])
    j = 2: nums[2] = 0, dp[4] = max(3,1+1) = 3 (子序列 [0,1,2])
    j = 3: nums[3] = 3, 继续遍历 (不满足递增)

youngyangyang04 / leetcode-master-comment

[Vssue]0300.最长上升子序列.md #146