找到最长的非递减序列

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

我没有看到你的算法有任何回溯,它似乎适用于非递减数字的连续块.如果我理解正确,请输入以下内容:

1 2 3 4 10 5 6 7

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

尝试使用动态编程找到解决方案.