algorithm - 最大化数组中之字形序列的数量

Question

我想最大化数组中之字形序列的数量(无需重新排序)。

我有一个随机整数序列的主数组。我想要一个具有锯齿形图案的主数组索引的子数组。

如果整数序列的每个元素都严格小于或严格大于其邻居(以及两个相邻的邻居)，则该整数序列称为之字形序列。

示例:序列 4 2 3 1 5 2 形成锯齿形，但 7 3 5 5 2 和 3 8 6 4 5 而 4 2 3 1 5 3 不要。

对于给定的整数数组，我们需要找到(连续的)索引子数组，形成锯齿形序列。

这可以在 O(N) 中完成吗？

Answer 1

是的，这似乎可以在 O(n) 时间内解决。我将把该算法描述为一个动态程序。

设置

将包含潜在之字形的数组称为Z .

让U是一个数组，使得 len(U) == len(Z) , 和 U[i]是一个整数，表示从 i 开始的最大的从左到右的连续子序列这是一个之字形，使得 Z[i] < Z[i+1] (曲折上升)。

让D类似于 U , 除了 D[i]是一个整数，表示从 i 开始的最大的从左到右的连续子序列这是一个之字形，使得 Z[i] > Z[i+1] (它向下倾斜)。

子问题

子问题是同时找到 U[i]和 D[i]在每个 i .这可以按如下方式完成:

U[i] = {
    1 + D[i+1]   if i < i+1
    0            otherwise
}

L[i] = {
    1 + U[i+1]   if i > i+1
    0            otherwise
}

顶层版本说如果我们正在寻找以向上之字形开头的最大序列，我们会查看下一个元素是否更大(向上)，然后将单个之字形添加到下一个向下的大小-锯齿序列。下一个是相反的。

基本案例

如果i == len(Z) (它是最后一个元素)，U[i] = L[i] = 0 .最后一个元素后面不能有从左到右的顺序，因为它后面没有任何内容。

解决方案

为了得到解决方案，首先我们找到max(U[i])和 max(L[i])对于每个 i .然后获取这两个值中的最大值，存储 i ，并存储这个最大之字形的长度(在一个名为 length 的变量中)。该序列从索引 i 开始并以索引 i + length 结束.

运行时

有n个索引，所以U之间有2n个子问题和 L .每个子问题都需要 O(1) 的时间来解决，因为之前解决的子问题的解决方案已被记住。最后，遍历 U和 L得到最终答案需要 O(2n) 的时间。

因此我们有 O(2n) + O(2n) 时间，或 O(n)。

这可能是一个过于复杂的解决方案，但它表明它可以在 O(n) 内完成。