c++ - 从c ++中给定的未排序整数向量中获取最长排序元素序列的最简单方法

Question

我有一个未排序的数组，需要提取最长的排序元素序列。例如

A = 2,4,1,7,4,5,0,8,65,4,2,34

这里 0,8,65 是我的目标序列

我需要跟踪这个序列开始的索引

Answer 1

您可以O(N)使用此算法在线性时间内完成：构造与原始向量len相同大小N的向量，其中包含元素所属len[i]的最长连续上升运行的长度。seq[i]

的值len[i]可以计算如下：

len[0] = 1;
for (int i = 1 ; i != N ; i++) {
    len[i] = seq[i-1] >= seq[i] ? 1 : len[i-1]+1;
}

len用手，找到max(len)元素的索引。这是你跑步的最后一个元素。回溯以len[j] == 1找到运行的初始元素。

seq    len
---    ---
  2      1
  4      2
  1      1
  7      2
  4      1
  5      2
  0      1
  8      2
 65      3 << MAX
  4      1
  2      1
 34      2

请注意，在算法的每个步骤中，您只需要len[i-1]计算的元素len，因此您可以通过删除 的向量表示len并保留前一个的max_len和来优化常数空间max_len_index。

这是针对恒定空间优化的算法。变量len表示len[i-1]来自线性空间算法。

int len = 1, pos = 0, maxlen = 1, current_start = 0;
for (int i = 1 ; i < seq.size() ; i++) {
    if (seq[i] > seq[i-1]) {
        len++;
        if (len > maxlen) {
            maxlen = len;
            pos = current_start;
        }
    } else {
        len = 1;
        current_start = i;
    }
}

这是ideone 上该程序的链接。

Answer 2

您需要 4 个索引（开始、结束、tmp_begin、tmp_end）。tmp_begin使用,作为工作索引遍历原始数组，tmp_end每次找到更长的排序序列更新begin和end索引。

要检查子序列是否已排序，您必须检查 i 处的元素是否大于 i 处的元素——对于子序列中的每对连续项。

最后：打印原始数组中从 开始到begin结束的所有元素end。

Answer 3

for(int i=0;i<size_of_array;i++)
{
  iterate++;
  after=array[iterate];
  if(after>before) {current_counter++;} else {current_counter=0;}
  if(max_counter<current_counter) max_counter=current_counter;
  before=array[iterate];
}

printf(" maximum length=%i ",max_counter);