V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
lsmgeb89
V2EX  ›  算法

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

  •  
  •   lsmgeb89 · 2017-03-18 04:30:44 +08:00 · 4322 次点击
    这是一个创建于 2568 天前的主题,其中的信息可能已经有所发展或是发生改变。

    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

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

    26 条回复    2017-03-19 09:20:06 +08:00
    lsmgeb89
        1
    lsmgeb89  
    OP
       2017-03-18 04:31:53 +08:00
    Valyrian
        2
    Valyrian  
       2017-03-18 06:38:19 +08:00
    即使真能写出来逻辑也很会很杂乱。。这个问题不美。。
    lsmgeb89
        3
    lsmgeb89  
    OP
       2017-03-18 07:24:42 +08:00 via Android
    @Valyrian 确实不美
    mkdong
        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],维护奇数结尾和偶数结尾两个单调队列,每次从中二分
    jininij
        5
    jininij  
       2017-03-18 12:22:20 +08:00 via Android
    https://ooo.0o0.ooo/2017/03/18/58ccb50acb07e.png

    在回家的长途客车上,没有运行,谁运行一下看看符不符合要求。
    复杂度 O(n)。一次循环。如果我题目没有理解错的话。
    jininij
        6
    jininij  
       2017-03-18 12:27:43 +08:00 via Android
    是求一个序列的最长 AMS 子序列还是求这个数字集合可以排列成的最长 AMS ?
    jininij
        7
    jininij  
       2017-03-18 12:35:08 +08:00 via Android
    如果是求这个数字集合可以排列成的最长 AMS ,仍然可以在两次循环中得到结果。第一次循环把集合拆开成偶数集合和奇数集合,然后对两个集合各自进行排序。
    现在有了一个递增的奇数数组,一个递增偶数数组,在两个数组 0 位置设置指针,交替的在两个数组中,向后移动指针,读出满足要求的数,即可。
    lsmgeb89
        8
    lsmgeb89  
    OP
       2017-03-18 12:56:47 +08:00
    @jininij 最长 AMS 子序列
    lsmgeb89
        9
    lsmgeb89  
    OP
       2017-03-18 14:17:40 +08:00
    @mkdong 问下, f[i,0] 和 f[i, 1] 是固定 a[i] 为序列的结尾?所以 f[i,0] 和 f[i, 1] 里必定有一个为 0 ?
    rogerchen
        10
    rogerchen  
       2017-03-18 14:45:10 +08:00
    跟一般的单增子序列有什么区别,不就是更新 opt 的时候多检查一个条件。
    lsmgeb89
        11
    lsmgeb89  
    OP
       2017-03-18 14:47:08 +08:00
    @jininij 构造了一个例子就错了,如: 7, 9, 0, 1, 4
    lsmgeb89
        12
    lsmgeb89  
    OP
       2017-03-18 14:48:25 +08:00
    @rogerchen 多检查一个条件是 O(n^2),问你能不能 O(nlog(n))?
    mkdong
        13
    mkdong  
       2017-03-18 16:57:07 +08:00 via iPhone
    @lsmgeb89 是的,其中一个肯定是 0
    lsmgeb89
        14
    lsmgeb89  
    OP
       2017-03-18 20:46:03 +08:00 via Android
    @mkdong 这里两个队列没有单调性的吧。例如: 6, 5, 2, 4, 3
    sengxian
        15
    sengxian  
       2017-03-18 20:48:07 +08:00
    对值域维护两个线段树,一个存奇数,一个存偶数。线段树的位置 i 表示结尾值为 i 的最长奇偶交错递增子序列的最大长度。每次转移的时候,查询前缀最大值即可。复杂度 O(n\log n)。

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

    当然你嫌常数大,也可以用树状数组来维护前缀最大值。
    lsmgeb89
        16
    lsmgeb89  
    OP
       2017-03-18 21:36:10 +08:00 via Android
    @sengxian 谢谢,我想下。
    lksltjw
        17
    lksltjw  
       2017-03-18 21:38:33 +08:00
    @sengxian
    这样做可能需要离散化,但是写起来很清晰
    其实两个数组分开二分就行
    lsmgeb89
        18
    lsmgeb89  
    OP
       2017-03-18 21:53:58 +08:00 via Android
    @lksltjw 同 4 楼的解法?
    lksltjw
        19
    lksltjw  
       2017-03-18 21:58:33 +08:00
    @lsmgeb89 对(我刚看到 4 楼
    其实离散化也不麻烦, c++ 直接调用 sort 和 lower_bound
    sengxian
        20
    sengxian  
       2017-03-18 21:58:49 +08:00
    @lksltjw 确实,这样常数是最小的。
    lsmgeb89
        21
    lsmgeb89  
    OP
       2017-03-18 22:23:11 +08:00 via Android
    @lksltjw 还没怎么明白,这两个数组为什么是也是递增的?
    lksltjw
        22
    lksltjw  
       2017-03-18 23:32:05 +08:00
    @lsmgeb89
    不考虑奇偶性,考虑普通的 LIS
    f(i) 表示长度为 i 的时候结尾最小是多少,每次更新的时候是找小于当前数的最大的 f(i) 然后在 i+1 的位置更新,让 f(i+1)变为当前值
    lsmgeb89
        23
    lsmgeb89  
    OP
       2017-03-18 23:40:01 +08:00
    @lksltjw 恩,这个我明白。但是 4 楼的定义应该不是扩展的这种。他的定义是固定 a[i] 为结尾的序列。见我 9 楼的回复。
    lksltjw
        24
    lksltjw  
       2017-03-19 00:16:28 +08:00
    f(i, k) 表示 序列长度为 i ,结尾元素的奇偶性为 k
    lsmgeb89
        25
    lsmgeb89  
    OP
       2017-03-19 00:51:35 +08:00 via Android
    @lksltjw OK 。我的想法一也是这样。但是 维护这两个数组并不简单。例如 a[i] 是偶数。 Case 1: 有可能直接 replace 偶数数组的某个值, Case 2: 也有可能从奇数数组里找个末尾比它小的 append ,然后再 append 或 replace 到偶数数组里。还有数组里可能有一连串值是相等的,新的值来的时候,如果找到了这一串值可能都要修改。
    hd7771
        26
    hd7771  
       2017-03-19 09:20:06 +08:00 via Android
    单调递增子序列就有 nlogn 解法。改改条件就好,没什么区别。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   2836 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 27ms · UTC 14:36 · PVG 22:36 · LAX 07:36 · JFK 10:36
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.