simpest方法从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个索引(begin,end,tmp_begin,tmp_end).使用tmp_begin,tmp_end作为工作索引迭代原始数组,每次找到更长的排序序列更新begin和end索引.

要检查子序列是否已排序,您必须检查i中的元素是否大于i--中的元素 - 对于子序列中的每对连续项.

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