Find longest non-decreasing sequence

Given the following question,

Given an array of integers A of length n, find the longest sequence {i_1, ..., i_k} such that i_j < i_(j+1) and A[i_j] <= A[i_(j+1)] for any j in [1, k-1].

Here is my solution, is this correct?

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) > (开发者_JAVA技巧max_end - max_start) 
   max_end   = try_end;
   max_start = try_start;
endif

Somehow, I don't think this is a correct solution but I cannot find a counter-example that disapprove this solution.

anyone can help?

Thank you

I don't see any backtracking in your algorithm, and it seems to be suited for contiguous blocks of non-decreasing numbers. If I understand correctly, for the following input:

1 2 3 4 10 5 6 7

your algorithm would return 1 2 3 4 10 instead of 1 2 3 4 5 6 7.

Try to find a solution using dynamic programming.

You're missing the case where the condition is not broken at its last iteration:

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

You'll never promote try_start and try_end to max_start and max_end unless your condition is broken. You need to perform the same check at the end of the loop.

Well, it looks like you're finding the start and the end of the sequence, which may be correct but it wasn't what was asked. I'd start by reading http://en.wikipedia.org/wiki/Longest_increasing_subsequence - I believe this is the question that was asked and it's a fairly well-known problem. In general cannot be solved in linear time, and will also require some form of dynamic programming. (There's an easier n^2 variant of the algorithm on Wikipedia as well - just do a linear sweep instead of the binary search.)

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