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

Question

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

例如，如果数组是，7 4 8 9 3 5 2 1 然后 L = 6 为 7,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

等...