/*
* 300. Longest Increasing Subsequence QuestionEditorial Solution My Submissions
Total Accepted: 34958
Total Submissions: 99352
Difficulty: Medium
Given an unsorted array of integers, find the length of longest increasing subsequence.
For example,
Given [10, 9, 2, 5, 3, 7, 101, 18],
The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4. Note that there may be more than one LIS combination, it is only necessary for you to return the length.
Your algorithm should run in O(n2) complexity.
Follow up: Could you improve it to O(n log n) time complexity?
Credits:
Special thanks to @pbrother for adding this problem and creating all test cases.
Hide Company Tags Microsoft
Hide Tags Dynamic Programming Binary Search
Hide Similar Problems (M) Increasing Triplet Subsequence (H) Russian Doll Envelopes
*/
package dp;
import java.util.*;
public class LongestIncreasingSeq {
public int lengthOfLIS(int[] nums) {
if (nums == null || nums.length == 0)
return 0;
int[] dp = new int[nums.length]; // length of LIS : start from i
Arrays.fill(dp, 1);
int max = 0;
for (int i = 0; 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);
}
}
max = Math.max(max, dp[i]);
}
return max;
}
public static void main(String[] args) {
int[] nums = {};
LongestIncreasingSeq lis = new LongestIncreasingSeq();
System.out.println(lis.lengthOfLIS(nums));
}
}
300. Longest Increasing Subsequence
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
推荐阅读更多精彩内容
- Longest Increasing Subsequence给定一个数组，找出longest increasing...
- Given an unsorted array of integers, find the length of l...
- 问题描述 Given an unsorted array of integers, find the length...
- 从第一个开始检查，注意，并不是指连续的序列。详见题目：https://leetcode.com/problems/...
- d[i] i为结尾的最长递增子序列，d[0] = 1 ,d[i] 算出 [0,i) 找出d[i] > d[[0,i...
