这是一个创建于 2808 天前的主题，其中的信息可能已经有所发展或是发生改变。
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
主要是想法一的状态转移方程很难想清楚
 |
2
Valyrian 2017-03-18 06:38:19 +08:00
即使真能写出来逻辑也很会很杂乱。。这个问题不美。。
|
 |
4
mkdong 2017-03-18 10:30:10 +08:00 via iPhone  1
@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]，维护奇数结尾和偶数结尾两个单调队列，每次从中二分 |
 |
5
jininij 2017-03-18 12:22:20 +08:00 via Android
https://ooo.0o0.ooo/2017/03/18/58ccb50acb07e.png
在回家的长途客车上，没有运行，谁运行一下看看符不符合要求。 复杂度 O(n)。一次循环。如果我题目没有理解错的话。 |
|
6
jininij 2017-03-18 12:27:43 +08:00 via Android
是求一个序列的最长 AMS 子序列还是求这个数字集合可以排列成的最长 AMS ？
|
|
7
jininij 2017-03-18 12:35:08 +08:00 via Android
如果是求这个数字集合可以排列成的最长 AMS ，仍然可以在两次循环中得到结果。第一次循环把集合拆开成偶数集合和奇数集合，然后对两个集合各自进行排序。
现在有了一个递增的奇数数组，一个递增偶数数组，在两个数组 0 位置设置指针，交替的在两个数组中，向后移动指针，读出满足要求的数，即可。 |
 |
9
lsmgeb89 OP @mkdong 问下， f[i,0] 和 f[i, 1] 是固定 a[i] 为序列的结尾？所以 f[i,0] 和 f[i, 1] 里必定有一个为 0 ？
|
 |
10
rogerchen 2017-03-18 14:45:10 +08:00
跟一般的单增子序列有什么区别，不就是更新 opt 的时候多检查一个条件。
|
 |
15
sengxian 2017-03-18 20:48:07 +08:00
对值域维护两个线段树，一个存奇数，一个存偶数。线段树的位置 i 表示结尾值为 i 的最长奇偶交错递增子序列的最大长度。每次转移的时候，查询前缀最大值即可。复杂度 O(n\log n)。
本题与最长上升子序列并无较大差别，只需开 2 个线段树即可实现奇数／偶数的条件。 当然你嫌常数大，也可以用树状数组来维护前缀最大值。 |
 |
22
lksltjw 2017-03-18 23:32:05 +08:00
@lsmgeb89
不考虑奇偶性，考虑普通的 LIS f(i) 表示长度为 i 的时候结尾最小是多少，每次更新的时候是找小于当前数的最大的 f(i) 然后在 i+1 的位置更新，让 f(i+1)变为当前值 |
|
23
lsmgeb89 OP @lksltjw 恩，这个我明白。但是 4 楼的定义应该不是扩展的这种。他的定义是固定 a[i] 为结尾的序列。见我 9 楼的回复。
|
|
24
lksltjw 2017-03-19 00:16:28 +08:00
f(i, k) 表示 序列长度为 i ，结尾元素的奇偶性为 k
|
|
25
lsmgeb89 OP @lksltjw OK 。我的想法一也是这样。但是 维护这两个数组并不简单。例如 a[i] 是偶数。 Case 1: 有可能直接 replace 偶数数组的某个值， Case 2: 也有可能从奇数数组里找个末尾比它小的 append ，然后再 append 或 replace 到偶数数组里。还有数组里可能有一连串值是相等的，新的值来的时候，如果找到了这一串值可能都要修改。
|
 |
26
hd7771 2017-03-19 09:20:06 +08:00 via Android
单调递增子序列就有 nlogn 解法。改改条件就好，没什么区别。
|
Select Language