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

Question

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

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

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

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

Answer 1

您可以使用此算法在线性时间 O(N) 内完成:构建与原始大小相同的 N vector len vector ，使得 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，因此您可以通过删除 vector 来优化常量空间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;
    }
}

这里是 a link to this program on ideone .