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羊精， 從右往左掃描品嚣。
復(fù)雜度是 O(n ^ 2)
優(yōu)化到 O(n log n) ,想到了 binary search, 但是實(shí)在不知道怎么優(yōu)化均唉。
看了下答案癌淮。發(fā)現(xiàn)思維的起點(diǎn)不是我這個(gè)方法。
自己重寫(xiě)了下：
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
解法有點(diǎn)怪属桦。畫(huà)了好長(zhǎng)一段時(shí)間來(lái)理解熊痴。
tails[i] 描述的是 length = i + 1 的sub increasing sequence 中最小的值。只有這個(gè)最小聂宾，才有可能接上更多的數(shù)愁拭，使得總長(zhǎng)度最大。
于是給定一個(gè) nums[i], 我們需要找到亏吝，他可以作為哪些長(zhǎng)度的sub increasing sequence 的尾部。
binary search 就是找到這么一個(gè)位置：
tails[i - 1] < value <= nums[i], 然后更新 nums[i]
如果找不到盏混， 就代表這個(gè)數(shù)最大蔚鸥，可以加在當(dāng)前最長(zhǎng)的sub sequence 后面惜论，使得總長(zhǎng)度再長(zhǎng)一位。
差不多就這么一個(gè)意思止喷。
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;
}
}
更容易理解的一種寫(xiě)法馆类。
tails[i] 表示， 長(zhǎng)度為 i + 1的 increasing subsequence, 的最后一個(gè)數(shù)字弹谁。
所以如果 i + 1 > size, 那么我們需要擴(kuò)大這個(gè)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/
發(fā)現(xiàn)這種理解方法乾巧，比 diet pepsi 的更容易記住。
Anyway, Good luck, Richardo! -- 10/12/2016
