題目

給定數(shù)組arr，返回arr的最長遞增子序列

舉例：arr = [2,1,5,3,6,4,8,9,7]，返回的最長遞增子序列為[1,3,4,8,9]

要求：如果arr的長度為N，請實(shí)現(xiàn)時(shí)間復(fù)雜度為O(nlogn)的方法。

分析

這一題也是經(jīng)典的動態(tài)規(guī)劃，那么常規(guī)的動態(tài)規(guī)劃時(shí)間復(fù)雜度為O(n^2);

如果加入二分的話，可以將動態(tài)規(guī)劃優(yōu)化到O(nlogn)。

解法1 O(n^2)的動態(tài)規(guī)劃

了解題目以后，狀態(tài)為數(shù)組的當(dāng)前位置i就能決定返回值，那么dp[i]表示arr[0...i]的最長遞增子序列

dp[i] = max{dp[i], dp[j]+1} (0<=j<i && arr[i]>arr[j])

// dp O(n^2) int* getdp1(int arr[], int length){int* dp= new int[length];for(int i=0;i<length;i++){dp[i]=1;for(int j=0;j<i;j++){dp[i] = max(dp[i], dp[j]+1);}}return dp; }

如果還需要求出遞增序列的話，可以這么做：

首先我們arr從右往左找出最大值，然后根據(jù)這個(gè)最大值往前遞推，滿足：

• arr[j] < arr[i] && dp[i] = dp[j] +1

這種遞推會推出一種特殊的情況，如果要找出所有的情況，就要再加一個(gè)循環(huán)。

解法2 O(nlogn)的動態(tài)規(guī)劃

我們在上面的查找過程中，一直都是在對arr進(jìn)行比較，那么可以通過空間換取時(shí)間，將遞增序列保存到數(shù)組中，然后對這個(gè)數(shù)組做二分查找。

舉例如下：

arr = [2,1,5,3,6,4,8,9,7]

采用ends[length+1]作為遞增序列數(shù)組，right記錄數(shù)組的長度

• 遍歷arr數(shù)組，arr[i]
• 查詢arr[i]在ends中的位置
  • 如果arr[i] 大于 ends[right]，那么直接將arr[i]加入ends，說明符合遞增
  • 否則用arr[i]替代調(diào)二分查找的位置（一直更新最小的結(jié)尾數(shù)）

詳細(xì)部分看代碼

int* getdp2(int arr[], int length){int* dp = new int[length+1];int* ends = new int[length+1];ends[0] = arr[0];dp[0] =1;int right = 0;int l =0;int r = 0;int m =0;for(int i=1;i<length;i++){l=0;r=right;while(l<=r){m = l + (r-l)/2;if(arr[i]>ends[m]) {l=m+1;}else{r=m-1;}}right = max(l,right);ends[l] = arr[i];dp[i] = l+1;}return dp; }

Conclusion

這一個(gè)題目的動態(tài)規(guī)劃優(yōu)化是采用了二分來優(yōu)化，是采用空間換時(shí)間；

之前還有路徑壓縮，縮小空間復(fù)雜度的題目 機(jī)器人到達(dá)指定位置方法數(shù)

總結(jié)

以上是生活随笔為你收集整理的最长单调递增子序列_最长递增子序列（动态规划 + 二分搜索）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。