本題用動態(tài)規(guī)劃和二分查找可解
一古涧、題目
給定一個無序的整數(shù)數(shù)組垂券，找到其中最長上升子序列的長度。
示例:
輸入: [10,9,2,5,3,7,101,18]
輸出: 4
解釋: 最長的上升子序列是 [2,3,7,101]蒿褂，它的長度是 4圆米。
說明:
可能會有多種最長上升子序列的組合，你只需要輸出對應的長度即可啄栓。你算法的時間復雜度應該為 O(n^2) 。
進階:你能將算法的時間復雜度降低到 O(n log n) 嗎?
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/longest-increasing-subsequence
二也祠、分析
2.1 題目分析
原始的數(shù)組是一個無序數(shù)組昙楚，要從無序數(shù)組中找到最長上升子序列。這個子序列的元素在原始數(shù)組中不要求是連續(xù)的诈嘿，并且子序列的元素必須是嚴格遞增的堪旧。
也就是說如果原始數(shù)組是 [10,9,2,5,3,7,101,18]削葱，那么 [2,3,7,101]就是一個最長的上升子序列。
2.2 回溯淳梦？
如果我們用回溯法來遍歷數(shù)組析砸，時間復雜度是2^n次方，這是不能接收的爆袍。
2.3 動態(tài)規(guī)劃
既然題目要求的是最長子序列的長度首繁，那么我們可以使用動態(tài)規(guī)劃，啟動dp[i]保存的就是以第 i個數(shù)字結(jié)尾的最長子序列的長度陨囊。
也就是說弦疮，如果原始數(shù)組src [] = {10, 3, 5, 2};
則dp[] 應為是 {1, 1, 2, 1}
我們應該把狀態(tài)轉(zhuǎn)移公式求出來。
基于上面的公式蜘醋，我們可以寫出下面的代碼
public int lengthOfLIS(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int[] dp = new int[nums.length]; //記錄以第i個數(shù)組結(jié)尾的最長上升序列
int res = 0;
for (int i = 0; i < nums.length; i++) {
dp[i] = 1;
for (int j = 0; j < i; j++) { // dp[i] = max(dp[j] + 1) && dp[j] < dp[i] && 0 <= j < i
if (nums[j] < nums[i]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
res = Math.max(res, dp[i]);
}
return res;
}
代碼的時間復雜度是 n^2
2.4 動態(tài)規(guī)劃+二分查找
如果將時間復雜度提高到nlogn胁塞，那么就需要修改一下思路。
我們用dp[i]保存所有長度為i + 1的上升序列的最后一個元素中最小的那一個压语。
因此啸罢，對于src[] = {10, 9, 2, 5, 3, 7, 101, 18}
遍歷數(shù)組，dp對應為
i = 0 dp = {10}
i = 1 dp = {9}
i = 2 dp = {2}
i = 3 dp = {2, 5}
i = 4 dp = {2, 3}
i = 5 dp = {2, 3, 7}
i = 6 dp = {2, 3, 7, 101}
i = 7 dp = {2, 3, 7, 18}
由于dp數(shù)組是嚴格上升的胎食，那么我們可以用二分查找的方式更新dp數(shù)組扰才，這樣總的時間復雜度就是nlogn。
代碼如下
public int lengthOfLIS(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int[] dp = new int[nums.length]; // dp[i] 標識所有長度為i+1的序列中斥季，最小的序列尾數(shù)
int maxLen = 1;
dp[0] = nums[0];
for (int cur : nums) {
if (cur > dp[maxLen - 1]) {
dp[maxLen] = cur;
maxLen++;
} else {
int start = 0;
int end = maxLen - 1;
while (start < end) { //二分查找
int mid = (start + end) /2;
if (cur > dp[mid]) {
start = mid + 1;
} else {
end = mid;
}
}
dp[start] = cur;
}
}
return maxLen;
}
