[讨论] 最长奇偶交错单调递增子序列

[lsmgeb89]

An alternating monotonic sequence (AMS) is a monotonically increasing sequence which alternates between even and odd numbers. For example, {7,12,13,22} is an AMS, but {7,12,14,21} is not (though it is a monotonic sequence). Describe a dynamic program for finding a longest alternating monotonic subsequence of a given sequence.

这是单调递增子序列的一个 follow-up 。

解法一 O(n^2)：可以改单调递增子序列的 O(n^2) 解法，在每次向前找的时候加上奇偶交错的条件。

代码： https://github.com/lsmgeb89/oj_solution/blob/master/others/ams/ams-0.cc

test ： https://github.com/lsmgeb89/oj_solution/blob/master/others/ams/test.txt

很容易实现，这个解法应该是对的。

那有没有 O(nlog(n)) 的解法？去尝试改单调递增子序列的 O(nlog(n)) 的 recurrence 。

想法一：

维护两个 list ，一个总是以偶数为结尾，一个总是以奇数为结尾。

每次 update 的时候交错 update 两个 list 。但是 update 的细节很难理清楚。

最后取两个 list 中最长的一个返回。

代码： https://github.com/lsmgeb89/oj_solution/blob/master/others/ams/ams-1.cc

这个代码过不了那个长度为 1000 的序列的 case ，只差一点，但感觉代码越写越乱，不高兴再查了。正确性存疑。

想法二：

同样维护两个 list 。

第一个 list 的第 0 个 element 是以奇数结尾的子序列，第 1 个 element 是以偶数结尾的子序列，以此类推。

第二个 list 的第 0 个 element 是以偶数结尾的子序列，第 1 个 element 是以奇数结尾的子序列，以此类推。

每次 update 各自的 list 。

最后取两个 list 中最长的一个返回。

代码： https://gist.github.com/lsmgeb89/f686e624855229c90c82de0bc52613b2

感觉正确性不对。因为稍长的 case 就过不了。

例如： 28, 26, 19, 29, 17, 20, 25, 14, 9, 5, 30, 6, 15, 18, 11, 16, 23, 8, 4, 27

主要是想法一的状态转移方程很难想清楚

[lsmgeb89]

@jedihy

[Valyrian]

即使真能写出来逻辑也很会很杂乱。。这个问题不美。。

[lsmgeb89]

@Valyrian 确实不美

[mkdong]

@lsmgeb89 没怎么看代码，但原理不算很复杂吧， f[i,0]表示 a[i]结尾为，结尾为偶数的 ams 的长度。 f[i,1]同理为结尾为奇数的 ams 长度。 f[i,k]=max{0, max{1+f[j,1-k] | j<i and a[j]<a[i] and a[i]%2=k}} k=0,1
为了快速找到最大 f[j,1-k]，维护奇数结尾和偶数结尾两个单调队列，每次从中二分

[jininij]

https://ooo.0o0.ooo/2017/03/18/58ccb50acb07e.png

在回家的长途客车上，没有运行，谁运行一下看看符不符合要求。
复杂度 O(n)。一次循环。如果我题目没有理解错的话。

[jininij]

是求一个序列的最长 AMS 子序列还是求这个数字集合可以排列成的最长 AMS ？

[jininij]

如果是求这个数字集合可以排列成的最长 AMS ，仍然可以在两次循环中得到结果。第一次循环把集合拆开成偶数集合和奇数集合，然后对两个集合各自进行排序。
现在有了一个递增的奇数数组，一个递增偶数数组，在两个数组 0 位置设置指针，交替的在两个数组中，向后移动指针，读出满足要求的数，即可。

[lsmgeb89]

@jininij 最长 AMS 子序列

[lsmgeb89]

@mkdong 问下， f[i,0] 和 f[i, 1] 是固定 a[i] 为序列的结尾？所以 f[i,0] 和 f[i, 1] 里必定有一个为 0 ？

[rogerchen]

跟一般的单增子序列有什么区别，不就是更新 opt 的时候多检查一个条件。

[lsmgeb89]

@jininij 构造了一个例子就错了，如： 7, 9, 0, 1, 4

[lsmgeb89]

@rogerchen 多检查一个条件是 O(n^2)，问你能不能 O(nlog(n))？

[mkdong]

@lsmgeb89 是的，其中一个肯定是 0

[lsmgeb89]

@mkdong 这里两个队列没有单调性的吧。例如： 6, 5, 2, 4, 3

[sengxian]

对值域维护两个线段树，一个存奇数，一个存偶数。线段树的位置 i 表示结尾值为 i 的最长奇偶交错递增子序列的最大长度。每次转移的时候，查询前缀最大值即可。复杂度 O(n\log n)。

本题与最长上升子序列并无较大差别，只需开 2 个线段树即可实现奇数／偶数的条件。

当然你嫌常数大，也可以用树状数组来维护前缀最大值。

[lsmgeb89]

@sengxian 谢谢，我想下。

[lksltjw]

@sengxian
这样做可能需要离散化，但是写起来很清晰
其实两个数组分开二分就行

[lsmgeb89]

@lksltjw 同 4 楼的解法？

[lksltjw]

@lsmgeb89 对（我刚看到 4 楼
其实离散化也不麻烦， c++ 直接调用 sort 和 lower_bound

[sengxian]

@lksltjw 确实，这样常数是最小的。