# O(nlogn) and O(n^2) Java Solutions

•  public class Solution {
// O(n^2) Solution
public int lengthOfLIS(int[] nums) {
int N = nums.length;
if (N == 0) return 0;
int[] dp = new int[N];
Arrays.fill(dp, 1);
int res = 1;
for (int i = 1; i < N; i++) {
for (int j = 0; j < i; j++) {
if (nums[j] < nums[i]) {
dp[i] = Math.max(dp[j] + 1, dp[i]);
}
}
res = Math.max(res, dp[i]);
}
return res;
}
// O(n^log(n)) Solution.
// http://www.geeksforgeeks.org/longest-monotonically-increasing-subsequence-size-n-log-n/
public int lengthOfLIS(int[] nums) {
if (nums.length == 0) return 0;
int len = 0, N = nums.length;
int[] tailTable = new int[N];
tailTable[len++] = nums[0];
for (int i = 1; i < N; i++) {
if (nums[i] < tailTable[0]) tailTable[0] = nums[i];
else if (nums[i] > tailTable[len - 1]) tailTable[len++] = nums[i];
else {
tailTable[binarySearch(tailTable, 0, len - 1, nums[i])] = nums[i];
}
}
return len;
}
private int binarySearch(int[] tails, int start, int end, int target) {
while (start < end) {
int mid = start + (end - start)/2;
if (tails[mid] >= target) end = mid;
else start = mid + 1;
}
return end;
}
}

• Why do I need to fill dp with 1? Can't I do dp[0] = 1 before the loop?

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.