給定一個(gè)整數(shù)序列，找到最長(zhǎng)上升子序列（LIS），返回LIS的長(zhǎng)度埠通。
說明
最長(zhǎng)上升子序列的定義：
最長(zhǎng)上升子序列問題是在一個(gè)無序的給定序列中找到一個(gè)盡可能長(zhǎng)的由低到高排列的子序列骑祟，這種子序列不一定是連續(xù)的或者唯一的。
https://en.wikipedia.org/wiki/Longest_increasing_subsequence
樣例
給出
[5,4,1,2,3]态贤，LIS 是[1,2,3]舱呻，返回3
給出[4,2,4,5,3,7]，LIS 是[2,4,5,7]抵卫，返回4
挑戰(zhàn)
要求時(shí)間復(fù)雜度為O(n^2) 或者 O(nlogn)
注意
動(dòng)態(tài)規(guī)劃求的是方案的個(gè)數(shù)而不是具體的方案狮荔，即求出最長(zhǎng)子序列的長(zhǎng)度，但最長(zhǎng)子序列究竟由哪些位置構(gòu)成無法得知
代碼
- 動(dòng)態(tài)規(guī)劃O(n ^ 2)
思路
本題屬于坐標(biāo)型動(dòng)態(tài)規(guī)劃介粘，也叫接龍型動(dòng)態(tài)規(guī)劃殖氏，但坐標(biāo)并沒有明顯給出，要想成為當(dāng)前元素的上一個(gè)坐標(biāo)需要滿足兩個(gè)條件：
a. 下標(biāo)位于當(dāng)前元素左邊
b. 數(shù)組中對(duì)應(yīng)的值小于當(dāng)前元素
數(shù)組當(dāng)中每一個(gè)元素都可以成為最長(zhǎng)序列的起點(diǎn)姻采，所以我們初始定義一個(gè) f 數(shù)組雅采，f[i] 記錄數(shù)組中相應(yīng)下標(biāo)對(duì)應(yīng)的最長(zhǎng)序列大小，初始化定義 f[i] = 1慨亲，如果存在下標(biāo) j 滿足上述 a 和 b 兩個(gè)條件且滿足 f[j] + 1 > f[i]婚瓜，即 f[j] 對(duì)應(yīng)的最長(zhǎng)序列接上 nums[j] 組成的新序列長(zhǎng)度大于 f[i]，那得到新的狀態(tài)刑棵，需要更新 f[i] 的值巴刻，f 數(shù)組中最大的值即為最長(zhǎng)上升子序列
狀態(tài)轉(zhuǎn)移方程為f[i] = max{1, f[j] + 1} (j = 1, 2, ..., i - 1, 且A[j] < A[i])
public class Solution {
/**
* @param nums: The integer array
* @return: The length of LIS (longest increasing subsequence)
*/
public int longestIncreasingSubsequence(int[] nums) {
// f數(shù)組存儲(chǔ)著當(dāng)前index對(duì)應(yīng)的最長(zhǎng)上升子序列
int []f = new int[nums.length];
int max = 0;
// 每個(gè)點(diǎn)都可以成為起點(diǎn)，初始化令f[i] = 1
// 如果只令f[0] = 1蛉签，代表只有index = 0才能做起點(diǎn)
for (int i = 0; i < nums.length; i++) {
f[i] = 1;
// index小于i且值小于nums[i]的數(shù)才能做為上一個(gè)點(diǎn)的候選
for (int j = 0; j < i; j++) {
if (nums[j] < nums[i]) {
f[i] = f[i] > f[j] + 1 ? f[i] : f[j] + 1;
}
}
// 從所有候選點(diǎn)里找到最長(zhǎng)的
if (f[i] > max) {
max = f[i];
}
}
return max;
}
}
- 二分法 O(log n)
思路
O(n^2)的算法復(fù)雜度高的原因就在于必須在1 ~ i-1中枚舉找到最大的 f[j] 的值才能最終更新f[i]的值胡陪，上一種算法的狀態(tài)轉(zhuǎn)移方程為 f[i] = max{1, f[j] + 1} (j = 1, 2, ..., i - 1, 且A[j] < A[i])沥寥，f[i] 代表當(dāng)前下標(biāo)對(duì)應(yīng)的最長(zhǎng)子序列。
現(xiàn)在柠座，我們仔細(xì)考慮計(jì)算 f[i] 時(shí)的情況邑雅。假設(shè)有兩個(gè)元素nums[x]和nums[y]，滿足
- x < y < i
- nums[x] < nums[y] < nums[i]
- f[x] = f[y]
此時(shí)妈经，選擇 f[x] 和選擇 f[y] 都可以得到同樣的 f[i] 值淮野，那么，在最長(zhǎng)上升子序列的這個(gè)位置中吹泡，應(yīng)該選擇nums[x]還是應(yīng)該選擇nums[y]呢骤星？
很明顯，選擇nums[x]比選擇nums[y]要好荞胡。如果在nums[x+1] ... nums[i-1]這一段中妈踊，如果存在nums[z]，nums[x] < nums[z] < nums[y]泪漂，則選擇nums[x]相比廊营，可能會(huì)得到更長(zhǎng)的上升子序列，當(dāng)前子序列構(gòu)成更長(zhǎng)子序列的潛力增大了萝勤。
如此露筒，我們根據(jù)數(shù)組 f 的值進(jìn)行分類。對(duì)于數(shù)組 f 的每一個(gè)取值k敌卓，我們只需要保留滿足f[i] = k的所有nums中的最小值慎式。用數(shù)組minLast記錄這個(gè)值，即minLast[k] = min{nums[i]} (f[i] = k) (minLast數(shù)組中元素按升序存儲(chǔ))
我們?cè)诒闅vnums數(shù)組的過程中趟径，將在minLast數(shù)組中找到第一個(gè)大于當(dāng)前nums[i]的元素瘪吏，用nums[i]替換該元素就可以實(shí)現(xiàn)剛剛說的記錄滿足f[i] = k的所有nums元素中的最小值 (nums中元素是順序遍歷，minLast元素剛剛大于nums[i]說明它們?cè)趎ums之間的所有元素都大于nums[i]蜗巧，也就意味著從minLast中找出的當(dāng)前元素本身到nums[i]之間所有元素不能成為接龍中nums[i]的上一個(gè)元素掌眠，即minLast找出的當(dāng)前元素對(duì)應(yīng)的f數(shù)組值和f[i]是相等的)
因?yàn)槲覀儗?duì)minLast的替換操作，遍歷到數(shù)組最后minLast的長(zhǎng)度也就成為了最長(zhǎng)子序列的長(zhǎng)度幕屹，要說明的是由于動(dòng)態(tài)規(guī)劃的特性我們得到的minLast并不是真正的接龍方案蓝丙，因?yàn)閷?shí)際接龍?zhí)暨x元素時(shí)nums數(shù)組元素的順序不能改變，而minLast元素的順序是插入得到的望拖，所以minLast中的元素并不是實(shí)際方案
public class Solution {
/**
* @param nums: The integer array
* @return: The length of LIS (longest increasing subsequence)
*/
public int longestIncreasingSubsequence(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
// 二分法尋找的是end位置渺尘，所以minLast數(shù)組至少要有兩個(gè)元素才能進(jìn)行插入更新值
// 所以minLast數(shù)組要多加一個(gè)元素
// 實(shí)際上minLast[0]會(huì)一直保持Integer.MIN_VALUE不變
int[] minLast = new int[nums.length + 1];
minLast[0] = Integer.MIN_VALUE;
for (int i = 1; i <= nums.length; i++) {
minLast[i] = Integer.MAX_VALUE;
}
for (int i = 0; i < nums.length; i++) {
// find the first number in minLast >= nums[i]
int index = binarySearch(minLast, nums[i]);
minLast[index] = nums[i];
}
for (int i = nums.length; i >= 1; i--) {
if (minLast[i] != Integer.MAX_VALUE) {
return i;
}
}
return 0;
}
// find the first number > num
private int binarySearch(int[] minLast, int num) {
int start = 0, end = minLast.length - 1;
while (start + 1 < end) {
int mid = (end - start) / 2 + start;
if (minLast[mid] < num) {
start = mid;
} else {
end = mid;
}
}
return end;
}
}
