[Leetcode] 300. Longest Increasing Subsequence
1430 ワード
Given an integer array nums, return the length of the longest strictly increasing subsequence.
A subsequence is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements. For example, [3,6,2,7] is a subsequence of the array [0,3,1,6,2,2,7].
A subsequence is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements. For example, [3,6,2,7] is a subsequence of the array [0,3,1,6,2,2,7].
Code
class Solution {
public int lengthOfLIS(int[] nums) {
int[] dp = new int[nums.length];
dp[0] = 1;
int max = 1;
for(int i=1 ; i<nums.length ; i++) {
dp[i] = 1;
for(int j=i-1 ; j>=0 ; j--) {
if(nums[i]>nums[j]) {
dp[i] = Math.max(dp[i], dp[j]+1);
}
}
max = Math.max(max, dp[i]);
}
return max;
}
}
Reference
この問題について([Leetcode] 300. Longest Increasing Subsequence), 我々は、より多くの情報をここで見つけました https://velog.io/@ujone/Leetcode-300.-Longest-Increasing-Subsequenceテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol