具有交替增加和减少值的最长子序列

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

等等...