1. Runtime Distribution
2. Submission Details
3. Description
Given an unsorted array of integers, find the length of longest increasing subsequence.
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?
4. Example
Given [10, 9, 2, 5, 3, 7, 101, 18],
The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4
5. Code
java
import java.util.Arrays;
import org.junit.Test;
public class LeetCode0300 {
public int lengthOfLIS(int[] nums) {
int dp[] = new int[nums.length];
int length = 0;
for (int i = 0; i < nums.length; i++) {
int index = Arrays.binarySearch(dp, 0, length, nums[i]);
if (index < 0) {
index = -index - 1;
}
dp[index] = nums[i];
if (index == length) {
length++;
}
}
return length;
}
@Test
public void test() {
int[] nums = { 10, 9, 2, 5, 3, 7, 101, 18 };
System.out.println(lengthOfLIS(nums));
}
}
java
import org.junit.Test;
public class LeetCode0300 {
public int lengthOfLIS(int[] nums) {
int[] dp = new int[nums.length];
int length = 0;
for (int i = 0; i < nums.length; i++) {
if (length == 0 || dp[length - 1] < nums[i]) {
dp[length] = nums[i];
length++;
continue;
}
int left = 0, right = length - 1;
while (left < right) {
int mid = left + ((right - left) >> 1);
if (dp[mid] < nums[i]) {
left = mid + 1;
} else {
right = mid;
}
}
dp[left] = nums[i];
}
return length;
}
@Test
public void test() {
int[] nums = { 10, 9, 2, 5, 3, 7, 101, 18 };
System.out.println(lengthOfLIS(nums));
}
}
Comments | NOTHING