algorithm - 找到最长的非递减序列

Question

给出以下问题，

给定一个长度为 n 的整数数组 A，找到最长的序列 {i_1, ..., i_k} 使得 i_j < i_(j+1) 且 A[i_j] <= A[i_(j+1 )] 对于 [1, k-1] 中的任意 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

我在你的算法中没有看到任何回溯，它似乎适用于非递减数字的连续 block 。如果我理解正确，对于以下输入:

1 2 3 4 10 5 6 7

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

尝试使用 dynamic programming 找到解决方案.