Find longest non-decreasing sequence

Question

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) > (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

Answer 1

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.