查找最長非遞減序列

Question

鑑於以下問題，

鑑於長度爲n的一個整數數組，找到最長的序列{I_1，...，I_K}使得i_j < I_（J + 1 ）和[1，k-1]中的任意j的A [i_j] < = A [i_（j + 1）]。

這是我的解決方案，這是正確的嗎？

max_start = 0; // store the final result 
max_end = 0; 
try_start = 0; // store the initial result 
try_end = 0; 

FOR i=0; i<(A.length-1); i++ DO 
    if A[i] <= A[i+1] 
    try_end = i+1; // satisfy the condition so move the ending point 
    else    // now the condition is broken 
    if (try_end - try_start) > (max_end - max_start) // keep it if it is the maximum 
     max_end = try_end; 
     max_start = try_start; 
    endif 
    try_start = i+1; // reset the search 
    try_end = i+1; 
    endif 
ENDFOR 

// Checking the boundary conditions based on comments by Jason 
if (try_end - try_start) > (max_end - max_start) 
    max_end = try_end; 
    max_start = try_start; 
endif 

不知怎的，我不認爲這是一個正確的解決方案，但我不能找到一個反例是不同意這種解決方案。

任何人都可以提供幫助嗎？

謝謝

Answer 1

我沒有在你的算法中看到任何回溯，它似乎適用於連續的非遞減數字塊。如果我理解正確的話，以下輸入：

1 2 3 4 10 5 6 7 

你的算法將返回1 2 3 4 10而不是1 2 3 4 5 6 7。

嘗試使用dynamic programming找到解決方案。

Answer 2

你錯過了在那裏的條件並不在其最後一次迭代斷線的情況：

1, 3, 5, 2, 4, 6, 8, 10 

你永遠不會促進try_start和try_end到max_start和max_end除非你的條件是破碎。您需要在循環結束時執行相同的檢查。

Answer 3

那麼，它看起來像你找到序列的開始和結束，這可能是正確的，但它不是被問到的。我從閱讀http://en.wikipedia.org/wiki/Longest_increasing_subsequence開始 - 我相信這是被問及的問題，這是一個相當知名的問題。一般不能在線性時間內解決，並且還需要某種形式的動態編程。 （在維基百科上還有一個更簡單的n^2算法變體 - 只需做一次線性掃描而不是二進制搜索。）

Answer 4

#include <algorithm> 
#include <vector> 
#include <stdio.h> 
#include <string.h> 
#include <assert.h> 

template<class RandIter> 
class CompM { 
    const RandIter X; 
    typedef typename std::iterator_traits<RandIter>::value_type value_type; 
    struct elem { 
     value_type c; // char type 
     explicit elem(value_type c) : c(c) {} 
    }; 
public: 
    elem operator()(value_type c) const { return elem(c); } 
    bool operator()(int a, int b) const { return X[a] < X[b]; } // for is_sorted 
    bool operator()(int a, elem b) const { return X[a] < b.c; } // for find 
    bool operator()(elem a, int b) const { return a.c < X[b]; } // for find 
    explicit CompM(const RandIter X) : X(X) {} 
}; 

template<class RandContainer, class Key, class Compare> 
int upper(const RandContainer& a, int n, const Key& k, const Compare& comp) { 
    return std::upper_bound(a.begin(), a.begin() + n, k, comp) - a.begin(); 
} 

template<class RandIter> 
std::pair<int,int> lis2(RandIter X, std::vector<int>& P) 
{ 
    int n = P.size(); assert(n > 0); 
    std::vector<int> M(n); 
    CompM<RandIter> comp(X); 
    int L = 0; 
    for (int i = 0; i < n; ++i) { 
     int j = upper(M, L, comp(X[i]), comp); 
     P[i] = (j > 0) ? M[j-1] : -1; 
     if (j == L) L++; 
     M[j] = i; 
    } 
    return std::pair<int,int>(L, M[L-1]); 
} 

int main(int argc, char** argv) 
{ 
    if (argc < 2) { 
     fprintf(stderr, "usage: %s string\n", argv[0]); 
     return 3; 
    } 
    const char* X = argv[1]; 
    int n = strlen(X); 
    if (n == 0) { 
     fprintf(stderr, "param string must not empty\n"); 
     return 3; 
    } 
    std::vector<int> P(n), S(n), F(n); 
    std::pair<int,int> lt = lis2(X, P); // L and tail 
    int L = lt.first; 
    printf("Longest_increasing_subsequence:L=%d\n", L); 
    for (int i = lt.second; i >= 0; --i) { 
     if (!F[i]) { 
      int j, k = 0; 
      for (j = i; j != -1; j = P[j], ++k) { 
       S[k] = j; 
       F[j] = 1; 
      } 
      std::reverse(S.begin(), S.begin()+k); 
      for (j = 0; j < k; ++j) 
       printf("%c", X[S[j]]); 
      printf("\n"); 
     } 
    } 
    return 0; 
}