My code:
public class Solution {
public int lengthOfLIS(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int n = nums.length;
int[] dp = new int[n];
dp[n - 1] = 1;
int ret = 1;
for (int i = dp.length - 2; i >= 0; i--) {
int max = 1;
for (int j = i + 1; j < dp.length; j++) {
if (nums[j] > nums[i]) {
max = Math.max(max, 1 + dp[j]);
}
}
dp[i] = max;
ret = Math.max(ret, dp[i]);
}
return ret;
}
}
DP， 从右往左扫描。
复杂度是 O(n ^ 2)
优化到 O(n log n) ,想到了 binary search, 但是实在不知道怎么优化。
看了下答案。发现思维的起点不是我这个方法。
自己重写了下：
My code:
public class Solution {
public int lengthOfLIS(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int n = nums.length;
int[] tails = new int[n];
int size = 0;
for (int i = 0; i < n; i++) {
int begin = 0;
int end = size;
while (begin < end) {
int middle = begin + (end - begin) / 2;
if (nums[i] > tails[middle]) {
begin = middle + 1;
}
else {
end = middle;
}
}
tails[begin] = nums[i];
if (begin >= size) {
size++;
}
}
return size;
}
}
reference:
https://discuss.leetcode.com/topic/28738/java-python-binary-search-o-nlogn-time-with-explanation
解法有点怪。画了好长一段时间来理解。
tails[i] 描述的是 length = i + 1 的sub increasing sequence 中最小的值。只有这个最小，才有可能接上更多的数，使得总长度最大。
于是给定一个 nums[i], 我们需要找到，他可以作为哪些长度的sub increasing sequence 的尾部。
binary search 就是找到这么一个位置：
tails[i - 1] < value <= nums[i], 然后更新 nums[i]
如果找不到， 就代表这个数最大，可以加在当前最长的sub sequence 后面，使得总长度再长一位。
差不多就这么一个意思。
Anyway, Good luck, Richardo! -- 08/26/2016
My code:
public class Solution {
public int lengthOfLIS(int[] nums) {
int n = nums.length;
int[] tails = new int[n];
int size = 0;
for (int i = 0; i < nums.length; i++) {
int begin = 0;
int end = size - 1;
while (begin <= end) {
int mid = begin + (end - begin) / 2;
if (tails[mid] < nums[i]) {
begin = mid + 1;
}
else if (tails[mid] > nums[i]) {
end = mid - 1;
}
else {
begin = mid;
break;
}
}
tails[begin] = nums[i];
if (begin + 1 > size) {
size++;
}
}
return size;
}
}
更容易理解的一种写法。
tails[i] 表示， 长度为 i + 1的 increasing subsequence, 的最后一个数字。
所以如果 i + 1 > size, 那么我们需要扩大这个size
Anyway, Good luck, Richardo! -- 09/26/2016
My code:
public class Solution {
public int lengthOfLIS(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
List<Integer> list = new ArrayList<Integer>(nums.length);
for (int i = 0; i < nums.length; i++) {
if (list.size() == 0 || nums[i] > list.get(list.size() - 1)) {
list.add(nums[i]);
}
else {
int begin = 0;
int end = list.size() - 1;
while (begin <= end) {
int mid = begin + (end - begin) / 2;
if (list.get(mid) > nums[i]) {
end = mid - 1;
}
else if (list.get(mid) < nums[i]) {
begin = mid + 1;
}
else {
begin = mid;
break;
}
}
list.set(begin, nums[i]);
}
}
return list.size();
}
}
reference:
http://www.programcreek.com/2014/04/leetcode-longest-increasing-subsequence-java/
发现这种理解方法，比 diet pepsi 的更容易记住。
Anyway, Good luck, Richardo! -- 10/12/2016
