BiruLyu
8/10/2017 - 5:02 PM

## 300. Longest Increasing Subsequence(#).java

``````public class Solution {
public int lengthOfLIS(int[] a) {
int n = a.length;

if (n == 0) {
return 0;
}
int[] dp = new int[a.length];
int resultMax = 1;

dp[0] = 1;

for (int i = 1; i < n; i++) {
int currMax = 0;
for (int p= 0 ; p <= i-1; p++) {

if(a[i] > a[p]) {
currMax = Math.max(currMax, dp[p]);
}
}
dp[i] = currMax + 1;
resultMax = Math.max(resultMax, dp[i]);
}

return resultMax;
}
}``````
``````public class Solution {
public int lengthOfLIS(int[] nums) {
if (nums.length < 2) return nums.length;;
int[] array = new int[nums.length];
int i = 0, end = 0;
array[i++] = nums[0];
while(i < nums.length) {
if (nums[i] > array[end]) {
array[++end] = nums[i];
} else {
int left = 0, right = end;
while(left < right) {
int mid = left + (right - left) / 2;
if (array[mid] < nums[i]) {
left = mid + 1;
} else {
right = mid;
}
}
array[left] = nums[i];
}
i++;
}
return end + 1;
}
}``````
``````public class Solution {
private int findLess(List<Integer> res, int target) {
int l = 0, r = res.size() - 1;
while (l < r) {
int mid = l + (r - l) / 2;
int midNum = res.get(mid);
if (midNum == target) return mid;
else if (midNum > target) {
r = mid;
} else {
l = mid + 1;
}
}
return l;
}
public int lengthOfLIS(int[] nums) {
List<Integer> res = new ArrayList<>();
if (nums == null || nums.length < 1) return res.size();
int len = nums.length;
for (int num : nums) {
if (res.size() < 1 || (num > res.get(res.size() - 1))) {