我有一個整數數組A [1 ... N]。現在我想打印所有最長的減少子數。我經歷了大部分的教程,但所有的教程只打印一個LDS。假設LDS的長度是5,那麼大多數教程只打印一個長度爲5的LDS。 但我想打印所有可能的LDS。如何這樣做嗎?可以在O(nlongn)時間內完成。僞代碼會更有幫助。打印所有可能的最長減少的子序列
回答
這是比較容易理解的想法,如果你未優化從教程的算法,並使用更簡單的N^2
算法,它可以線性回溯而不是在地圖上查找。然後修改打印序列的代碼以向後搜索先前的元素,而不是將其存儲在vector<int> pre
中。然後你可以用簡單的遞歸回溯器打印所有序列:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void print_all(
const vector<int> seq
, const vector<int>& len
, int max, int pos
, vector<int>& sofar) {
if (max == 0) {
for (int i = sofar.size()-1 ; i >= 0 ; i--)
cout << sofar[i] << " ";
cout << endl;
return;
}
int val = pos < seq.size() ? seq[pos] : -1;
for (int i = pos-1 ; i >= 0 ; i--) {
if (len[i] == max && seq[i] > val) {
sofar.push_back(seq[i]);
print_all(seq, len, max-1, i, sofar);
sofar.erase(sofar.end()-1);
}
}
}
int main() {
int data[] = {5, 30, 2, 17, 92, 11, 7, 10, 2, 1};
vector<int> seq(data, data+10);
vector<int> len(seq.size());
for (int i = 0 ; i < seq.size() ; i++) {
len[i] = 1;
for (int j = i-1 ; j >= 0 ; j--)
if (seq[j] > seq[i] && len[j]+1 > len[i])
len[i] = len[j]+1;
}
int max = *max_element(len.begin(), len.end());
cerr << max << endl;
vector<int> sofar;
print_all(seq, len, max, seq.size(), sofar);
}
dasblinkenlight ::程序給出的病例數據不正確的輸出[] = {5,23,100,10,4,90,65,11,18,10},其給出的LDS長度= 4,並且LDS是 {90 65 18 10}, {90 65 11 10} 如何正確的答案是LDS長度= 5,並且LDS是 {100 90 65 18 10}, {100 90 65 11 10} – 2012-04-15 13:21:42
dasblinkenlight ::程序給出不正確的輸出數據[] = {5, 23,100,10,4,90,65,1 1,18,10},其LDS長度= 4,LDS是{90 65 18 10},{90 65 11 10}正確的答案是LDS長度= 5,LDS是{100 90 65 18 10} ,{100 90 65 11 10} – 2012-04-15 13:35:35
dasblinkenlight ::你可以在這裏查看:: http://ideone.com/SP4wc – 2012-04-15 13:44:56
您可以跟蹤你所有的時間最長(迄今爲止)的子序列,你走:
// If you have only one element, that is the longest descending subsequence
// Otherwise store first element as previous
if: current element is less than (or equal to) previous
// decreasing
increase current subsequence length
add element to current subsequence
else:
// increasing
set current subsequence length to 0
empty current subsequence
if: current subsequence is longer than current maximum
invalidate all current max subsequences
set current maximum subsequence length to current subsequence length
add current subsequence to set of longest subsequences
else if: current subsequence is same size as current maximum
add current subsequence to set of longest subsequences
- 1. 打印最長公共子序列
- 2. 所有可能的非遞減序列
- 3. 打印列表的所有可能的子集
- 4. 打印最長的常見序列
- 5. 如何打印數字的所有可能的序列n
- 6. 高效算法打印長度爲2到n + 1的所有可能子序列中元素的總和
- 7. 打印5x5矩陣到所有2 * 2可能的子矩陣
- 8. 有效地打印一個長序列
- 9. 查找長度爲k的所有遞減序列的列表?
- 10. 最長的子序列
- 11. 打印張數最長的序列號列表(蟒蛇)
- 12. 用所有行和所有列打印datagridview的最佳方法?
- 13. 最長的子序列的長度
- 14. 最長子序列
- 15. 如何在python中打印所有可能的嵌套列表?
- 16. 打印出每個陣列的所有可能性?
- 17. 是否可以使用WinHugs打印Haskell中的所有縮減?
- 18. 減少所有可能性的條件數
- 19. 如何打印來自給定數組的最長增量子序列(LIS)?
- 20. 如何減少散列值的長度?
- 21. 儘量減少實施可打印報告的難度
- 22. 查找最長非遞減序列
- 23. 所有可能的中間元素,用於字符串的最大奇數長度迴文子序列
- 24. 減少的Javascript子陣列單陣列
- 25. java中所有可能的子集不同的序列
- 26. 最佳長度的所有連續的子陣列
- 27. 如何打印多個字符的所有可能的組合?
- 28. 打印所有可能的8位數字的算法
- 29. 如何打印矩陣的所有列
- 30. Informix列的最大長度是多少?可以增加多少?
什麼教程?你到目前爲止有什麼?任何你有特定問題的代碼? – Femaref 2012-04-15 11:50:34
嘗試使用精美的數據結構,發佈一些示例代碼,展示您嘗試過的東西等。基本上_TRIE_ – Baz1nga 2012-04-15 11:55:14
@Femaref:https://comeoncodeon.wordpress.com/2009/08/12/longest-increasing-subsequence-lis /這是我所指的。這是雖然LIS,但它不會成熟很多。它只打印LAST LDS,如果倍數退出。我想要打印所有的LDS – 2012-04-15 11:55:57