V2EX = way to explore V2EX 是一个关于分享和探索的地方
Sign Up Now For Existing Member Sign In
This topic created in 3327 days ago, the information mentioned may be changed or developed.
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 Mar 18, 2017 即使真能写出来逻辑也很会很杂乱。。这个问题不美。。 |
 | 4 mkdong Mar 18, 2017 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 Mar 18, 2017 via Android https://ooo.0o0.ooo/2017/03/18/58ccb50acb07e.png 在回家的长途客车上，没有运行，谁运行一下看看符不符合要求。 复杂度 O(n)。一次循环。如果我题目没有理解错的话。 |
| 6 jininij Mar 18, 2017 via Android 是求一个序列的最长 AMS 子序列还是求这个数字集合可以排列成的最长 AMS ？ |
| 7 jininij Mar 18, 2017 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 Mar 18, 2017 跟一般的单增子序列有什么区别，不就是更新 opt 的时候多检查一个条件。 |
 | 15 sengxian Mar 18, 2017 对值域维护两个线段树，一个存奇数，一个存偶数。线段树的位置 i 表示结尾值为 i 的最长奇偶交错递增子序列的最大长度。每次转移的时候，查询前缀最大值即可。复杂度 O(n\log n)。 本题与最长上升子序列并无较大差别，只需开 2 个线段树即可实现奇数／偶数的条件。 当然你嫌常数大，也可以用树状数组来维护前缀最大值。 |
 | 22 lksltjw Mar 18, 2017 @lsmgeb89 不考虑奇偶性，考虑普通的 LIS f(i) 表示长度为 i 的时候结尾最小是多少，每次更新的时候是找小于当前数的最大的 f(i) 然后在 i+1 的位置更新，让 f(i+1)变为当前值 |
| 24 lksltjw Mar 19, 2017 f(i, k) 表示 序列长度为 i ，结尾元素的奇偶性为 k |
| 25 lsmgeb89 OP @lksltjw OK 。我的想法一也是这样。但是 维护这两个数组并不简单。例如 a[i] 是偶数。 Case 1: 有可能直接 replace 偶数数组的某个值， Case 2: 也有可能从奇数数组里找个末尾比它小的 append ，然后再 append 或 replace 到偶数数组里。还有数组里可能有一连串值是相等的，新的值来的时候，如果找到了这一串值可能都要修改。 |
 | 26 hd7771 Mar 19, 2017 via Android 单调递增子序列就有 nlogn 解法。改改条件就好，没什么区别。 |
Select Language