Tìm dài nhất không giảm chuỗi

Question

Với câu dưới đây,

Với một loạt các số nguyên A có độ dài n, tìm chuỗi dài nhất {i_1, ..., i_k} mà i_j < i_ (j + 1) và A [i_j] < = A [i_ (j + 1)] cho bất kỳ j nào trong [1, k-1].

Đây là giải pháp của tôi, điều này có đúng không?

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 

Bằng cách nào đó, tôi không nghĩ đây là giải pháp đúng nhưng tôi không thể tìm thấy ví dụ phản đối giải pháp này.

mọi người đều có thể trợ giúp?

Cảm ơn bạn

Answer 1

Tôi không thấy bất kỳ backtracking nào trong thuật toán của bạn và dường như nó phù hợp cho các khối liên tiếp của các số không giảm. Nếu tôi hiểu đúng, cho đầu vào sau:

1 2 3 4 10 5 6 7 

thuật toán của bạn sẽ trở 1 2 3 4 10 thay vì 1 2 3 4 5 6 7.

Cố gắng tìm giải pháp sử dụng dynamic programming.

Answer 2

Bạn đang thiếu trường hợp điều kiện không bị hỏng ở lần lặp cuối cùng của nó:

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

Bạn sẽ không bao giờ phát huy try_start và try_end-max_start và max_end trừ khi tình trạng của bạn là bị hỏng. Bạn cần thực hiện cùng một kiểm tra ở cuối vòng lặp.

Answer 3

Vâng, có vẻ như bạn đang tìm sự bắt đầu và kết thúc chuỗi, điều này có thể đúng nhưng đó không phải là những gì được hỏi. Tôi bắt đầu bằng cách đọc http://en.wikipedia.org/wiki/Longest_increasing_subsequence - Tôi tin rằng đây là câu hỏi được hỏi và đó là một vấn đề khá nổi tiếng. Nói chung không thể được giải quyết trong thời gian tuyến tính, và cũng sẽ yêu cầu một số hình thức lập trình năng động. (Có một biến thể n^2 của thuật toán trên Wikipedia cũng dễ dàng hơn - chỉ cần thực hiện quét tuyến tính thay vì tìm kiếm nhị phân.)

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; 
}