/
_300.java
executable file
·37 lines (33 loc) · 1019 Bytes
/
_300.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
package com.hit.basmath.interview.top_interview_questions.medium_collection.dynamic_programming;
import java.util.Arrays;
/**
* 300. Longest Increasing Subsequence
* <p>
* Given an unsorted array of integers, find the length of longest increasing subsequence.
* <p>
* Example:
* <p>
* Input: [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.
* <p>
* Note:
* <p>
* 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.
* <p>
* Follow up: Could you improve it to O(n log n) time complexity?
*/
public class _300 {
public int lengthOfLIS(int[] nums) {
int[] dp = new int[nums.length];
int len = 0;
for (int x : nums) {
int i = Arrays.binarySearch(dp, 0, len, x);
if (i < 0) i = -(i + 1);
dp[i] = x;
if (i == len) len++;
}
return len;
}
}