arrays - 具有交替递增和递减值的最长子序列

Question

给定一个数组，我们需要找到具有交替递增和递减值的最长子序列的长度。

例如，如果数组是 ， 7 4 8 9 3 5 2 1那么L = 6for7,4,8,3,5,2或7,4,9,3,5,1等。

也可能是首先我们有小元素然后大元素。

什么是最有效的解决方案？我想到了一个 DP 解决方案。如果我们要使用蛮力来做到这一点，我们会怎么做（O（n ^ 3）？）？

这不是作业问题。

Answer 1

您确实可以在这里使用动态编程方法。为了简单起见，假设我们只需要找到这样的序列seq的最大长度（很容易调整解决方案来找到序列本身）。

对于每个索引，我们将存储 2 个值：

• 在最后一步增加的那个元素处结束的交替序列的最大长度（例如，incr [i]）
• 在最后一步减少的那个元素处结束的交替序列的最大长度（例如，decr [i]）

同样根据定义，我们假设incr[0] = decr[0] = 1

然后可以递归地找到每个 incr[i] ：

incr[i] = max(decr[j])+1, where j < i and seq[j] < seq[i]
decr[i] = max(incr[j])+1, where j < i and seq[j] > seq[i]

所需的序列长度将是两个数组中的最大值，这种方法的复杂度是 O(N*N) 并且需要 2N 的额外内存（其中 N 是初始序列的长度）

c中的简单示例：

int seq[N]; // initial sequence
int incr[N], decr[N];

... // Init sequences, fill incr and decr with 1's as initial values

for (int i = 1; i < N; ++i){
    for (int j = 0; j < i; ++j){
         if (seq[j] < seq[i]) 
         {
             // handle "increasing" step - need to check previous "decreasing" value
             if (decr[j]+1 > incr[i])  incr[i] = decr[j] + 1;
         }
         if (seq[j] > seq[i]) 
         {
             if (incr[j]+1 > decr[i])  decr[i] = incr[j] + 1;
         }
    }
}

... // Now all arrays are filled, iterate over them and find maximum value

算法将如何工作：

第 0 步（初始值）：

seq  = 7   4 8 9 3 5 2 1
incr = 1   1 1 1 1 1 1 1
decr = 1   1 1 1 1 1 1 1

第 1 步在索引 1 ('4') 处取值并检查以前的值。7 > 4 所以我们使“从索引 0 到索引 1 的递减步长，新的序列值：

incr = 1 1   1 1 1 1 1 1
decr = 1 2   1 1 1 1 1 1

步骤 2.取值 8 并迭代先前的值：

7 < 8，增加步长：incr[2] = MAX(incr[2], decr[0]+1):

incr = 1 1 2   1 1 1 1 1
decr = 1 2 1   1 1 1 1 1

4 < 8，增加步长：incr[2] = MAX(incr[2], decr[1]+1)：

incr = 1 1 3   1 1 1 1 1
decr = 1 2 1   1 1 1 1 1

ETC...