Найти самую длинную неубывающую последовательность

Question

Учитывая следующий вопрос,

Учитывая массив целых чисел A длины n, найдите самую длинную последовательность {i_1, ..., i_k} такую, что i_j Вот мое решение, это правильно?

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.

Попробуйте найти решение, используя динамическое программирование .

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