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

求教各位 v 站大佬, [最大子数组] 这道题是否可进行优化?(望轻喷)

  •  
  •   qawsed2019 · 2019-05-24 10:11:13 +08:00 · 1980 次点击
    这是一个创建于 1997 天前的主题,其中的信息可能已经有所发展或是发生改变。

    描述

    给定一个整数数组和一个整数 k,找出 k 个不重叠子数组使得它们的和最大。每个子数组的数字在数组中的位置应该是连续的。返回最大的和。

    样例 1

    输入: 
    List = [1,2,3]
    k = 1
    输出: 6
    说明: 1 + 2 + 3 = 6
    

    样例 2

    输入:
    List = [-1,4,-2,3,-2,3]
    k = 2
    输出: 8
    说明: 4 + (3 + -2 + 3) = 8
    

    先说一下我的解题思路: 首先预处理前缀和,使 sum[i]代表以第 i 个数结尾的长度为 k 的子串和,方便计算区间的和。然后对三段的起始位置进行遍历,求和,时间复杂度是 O(n^3)。那么,如何优化呢?大家有没有建议? 请各位 v 站大佬轻喷(>人<;)

    13 条回复    2019-05-24 17:53:33 +08:00
    littlekui
        1
    littlekui  
       2019-05-24 10:19:35 +08:00   ❤️ 1
    评价你的解题思路:我只看懂了前缀和,之后的每个字都不知道你在说啥。。

    如果想要这道题的解答,可以参考下 Lintcode 上: https://www.lintcode.com/problem/maximum-subarray-iii/description#utm_source=v2exmn
    ZSeptember
        2
    ZSeptember  
       2019-05-24 10:44:03 +08:00
    这个?
    geelaw
        3
    geelaw  
       2019-05-24 10:59:00 +08:00 via iPhone   ❤️ 1
    很经典的动态规划问题,考虑 f(i, j) 表示前 i 个数拿 j 段且第 i 个数选中时能得到的最大和,g 则表示第 i 个数不选的情况,那么

    f(i, j) = max{ f(i-1, j) + a[i-1], g(i-1, j-1) + a[i-1] }
    g(i, j) = max{ f(i-1, j), g(i-1, j) }

    f(?, 0) = -infty
    g(?, 0) = 0

    答案 = max{ f(n, k), g(n, k) }

    令第一维滚动,可以得到 streaming 的算法,时间 O(nk),空间 O(k)。
    geelaw
        4
    geelaw  
       2019-05-24 11:00:53 +08:00 via iPhone
    @geelaw #3 Oops 状态转移的时候应该考虑两个相邻的段实际上是接起来的,一种方法是答案改成 max{ f(n, j), g(n, j) } over j<=k,另一种是虚拟地在中间插入 0。
    galahadv2
        5
    galahadv2  
       2019-05-24 11:04:48 +08:00   ❤️ 2
    《算法导论》 4.1 讲解了如何使用分治法求解最大子数组的问题,在练习题 4.1-5,提示了一个线性时间的算法。

    对于数组 A, 如果已经知道了 A[0:j] 的最大子数组,那么可以按如下性质扩展得到 A[0:j+1] 的最大子数组:
    ```
    A[0:j+1] 的最大子数组要么依然是 A[0:j] 的最大子数组,要么是某个子数组 A[i:j+1] (1<=i<=j+1>>)
    ```

    上面这句话也可以直观地理解为:
    ```
    A[0:j+1] 的最大子数组只有有两种可能情形:

    1. 依然是 A[0:j] 的最大子数组,它必定不包含 A[j] 这个元素(注意 a[j] 是 A[0:j+1] 的最后一个元素,并不包含在 A[0:j]中);
    2. 是一个位于最右边的子数组(A[i:j+1] 形式的)。
    ```
    因此在循环体中,每次都计算一下情形 2 的最大子数组,即计算必定包含最后一个元素的最大子数组(我们给它命名为最右最大子数组),然后和 A[0:j]相比较,较大的即为 A[0:j+1]的最大子数组。

    ``` golang
    func maxIncludeRight(a []int) int {
    sum := 0
    max := math.MinInt64
    for i := len(a) - 1; i >= 0; i-- {
    if sum += a[i]; sum >= max {
    max = sum
    }
    }
    return max
    }

    func maxSubArray(nums []int) int {
    max := nums[0]
    for i := range nums {
    if right := maxIncludeRight(nums[:i+1]); max < right {
    max = right
    }
    }
    return max
    }
    ```

    上面的代码已经可以正常工作了,现在来观察一下是否还有优化的余地。

    观察 maxIncludeRight ,每次它都全新地来计算“最大最右子数组”,实际上,如果我们已知 a[0:i]的“最右最大子数组”,那么可以很快求出 a[0:i+1]的“最大最右子数组”。方法如下:

    1. 如果 a[0:i]的最右最大子数组 m 小于 0,则 a[0:i+1]的最右最大子数组就是 a[i];
    2. 如果 a[0:i]的最右最大子数组 m 不小于 0,则 a[0:i+1]的最右最大子数组就是 m+a[i]。

    初始时,a[0:1]的最右最大子数组为 a[0], 这样可以一步步来求出 a[0:i]的最右最大子数组了。代码如下:

    ``` golang
    func maxIncludeRight(a []int, i int) int {
    max := a[0]
    for _, v := range a[1 : i+1] {
    if max < 0 {
    max = v
    } else {
    max += v
    }
    }
    return max
    }

    func maxSubArray(nums []int) int {
    max := nums[0]
    for i := range nums {
    if right := maxIncludeRight(nums, i); max < right {
    max = right
    }
    }
    return max
    }
    ```

    注意到两次循环可以合并,一次搞定,因此最终的代码如下:

    ```go
    func maxSubArray(nums []int) int {
    max, sum := nums[0], nums[0]
    for _, e := range nums[1:] {
    if sum < 0 {
    sum = e
    } else {
    sum += e
    }
    if sum >= max {
    max = sum
    }
    }
    return max
    }
    ```

    最后阅读上面这段代码,也可以换个角度来思考最大子数组问题。

    最大子数组必定满足这一性质:
    ```
    位于它左侧的任何一个子数组必定大于 0
    ```

    因为如果存在一个小于 0 的左侧子数组,则可以去掉它,而得到一个新的最大子数组。

    例如,对于[-2, 1, -3, 4, -1, 2, 1, -5, 4]:
    [-2, 1, -3]肯定不是最大子数组,因为左侧的 [-2, 1]小于 0
    从 4 开始往右,
    [4]
    [4,-1]
    [4, -1, 2]
    [4, -1, 2, 1]
    以上都有可能是最大子数组。

    [4, -1, 2, 1,-5] 不可能是最大子数组,因为它小于 0。

    因此,按此方法从左向右,舍弃所有已知左侧子数组小于 0 的情形,然后取最大值即可。
    qawsed2019
        6
    qawsed2019  
    OP
       2019-05-24 14:08:46 +08:00
    @ZSeptember 是否发了图片?貌似木有显示诶
    qawsed2019
        7
    qawsed2019  
    OP
       2019-05-24 14:09:10 +08:00
    @galahadv2 多谢~~~
    qawsed2019
        8
    qawsed2019  
    OP
       2019-05-24 14:09:56 +08:00
    @galahadv2 三克油,(>▽<)
    jxf2008
        9
    jxf2008  
       2019-05-24 14:12:14 +08:00
    ```
    for(int i = 0 ; i < k ; ++i)
    ```
    jxf2008
        10
    jxf2008  
       2019-05-24 14:12:38 +08:00
    发错。。。。不好意思
    qawsed2019
        11
    qawsed2019  
    OP
       2019-05-24 14:14:25 +08:00
    @jxf2008 啊咧(o_ _)ノ
    qawsed2019
        12
    qawsed2019  
    OP
       2019-05-24 14:15:11 +08:00
    @jxf2008 是不是故意来调戏的(lll ¬ω¬)
    ZSeptember
        13
    ZSeptember  
       2019-05-24 17:53:33 +08:00
    @qawsed2019 无视吧,看错题目了。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2939 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 32ms · UTC 13:02 · PVG 21:02 · LAX 05:02 · JFK 08:02
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.