LeetCode 300. Longest Increasing Subsequence
您是打尖儿还是住店呢
2023年03月13日 11:03
收录于文集
共500篇

Given an integer array , return the length of the longest strictly increasing subsequence.

 

Example 1:

Input: nums = [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.

Example 2:

Input: nums = [0,1,0,3,2,3]

Output: 4

Example 3:

Input: nums = [7,7,7,7,7,7,7]

Output: 1

 

Constraints:

  • 1 <= nums.length <= 2500

  • -104 <= nums[i] <= 104

  • dp判断即可，我单独写了函数就不能跑出来，把函数重新放回去，在主程序中就能过，应该传递的时候没有传递地址的原因。

代码块
JavaScript
自动换行
复制代码
class Solution {
    public int lengthOfLIS(int[] nums) {
        int n=nums.length;
        int[]dp=new int[n];
        dp[0]=1;
        for (int i = 1; i < dp.length; i++) {
            int max=0;
           for(int j=0;j<i;j++){
            if(nums[j]<nums[i]){
                max=Math.max(max, dp[j]);
            }
           }
            dp[i]=1+max;
        }
        int max_final=0;
        for (int i : dp) {
            max_final=Math.max(max_final, i);
        }
        return max_final;
    }
}
复制成功

Runtime: 55 ms, faster than 72.42% of Java online submissions for Longest Increasing Subsequence.

Memory Usage: 42.8 MB, less than 23.32% of Java online submissions for Longest Increasing Subsequence.

Leetcode
cv22368584