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

[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]

@lksltjw 还没怎么明白，这两个数组为什么是也是递增的？

[lksltjw]

@lsmgeb89
不考虑奇偶性，考虑普通的 LIS
f(i) 表示长度为 i 的时候结尾最小是多少，每次更新的时候是找小于当前数的最大的 f(i) 然后在 i+1 的位置更新，让 f(i+1)变为当前值

[lsmgeb89]

@lksltjw 恩，这个我明白。但是 4 楼的定义应该不是扩展的这种。他的定义是固定 a[i] 为结尾的序列。见我 9 楼的回复。

[lksltjw]

f(i, k) 表示 序列长度为 i ，结尾元素的奇偶性为 k

[lsmgeb89]

@lksltjw OK 。我的想法一也是这样。但是 维护这两个数组并不简单。例如 a[i] 是偶数。 Case 1: 有可能直接 replace 偶数数组的某个值， Case 2: 也有可能从奇数数组里找个末尾比它小的 append ，然后再 append 或 replace 到偶数数组里。还有数组里可能有一连串值是相等的，新的值来的时候，如果找到了这一串值可能都要修改。

[hd7771]

单调递增子序列就有 nlogn 解法。改改条件就好，没什么区别。