跳转到内容

最大子数列问题：修订间差异

维基百科，自由的百科全书
下一版本→
删除的内容 添加的内容
可视化wikitext
Liangdahanay（留言 | 贡献）
7次编辑
←建立内容为“在计算机科学中，最大子数列问题的目标是在数列的一维方向找到一个连续的子数列，使该子数列的和最大。...”的新页面
（没有差异）

2014年10月2日 (四) 19:28的版本

在计算机科学中，最大子数列问题的目标是在数列的一维方向找到一个连续的子数列，使该子数列的和最大。例如，对一个数列 −2, 1, −3, 4, −1, 2, 1, −5, 4，其连续子数列中和最大的是 4, −1, 2, 1, 其和为6。

该问题最初由布朗大学的Ulf Grenander教授于1977年提出，当初他为了展示数字图像中一个简单的最大然似然估计模型。不久之后卡耐基-梅隆大学的Jay Kadane提出了该问题的线性算法。（Bentley 1984）。

Kadane算法

Kadane算法扫描一次整个数列的所有数值，在每一个扫描点计算以该点数值为结束点的子数列的最大和（正数和）。该子数列有可能为空，或者由两部分组成：以前一个位置为结束点的最大子数列、该位置的数值。可用如下代码表示，这里用到了Python: 

def max_subarray(A):
    max_ending_here = max_so_far = 0
    for x in A:
        max_ending_here = max(0, max_ending_here + x)
        max_so_far = max(max_so_far, max_ending_here)
    return max_so_far

该问题的一个变种是：如果数列中含有负数元素，不允许返回长度为零的子数列。该问题可用如下代码解决： 

def max_subarray(A):
    max_ending_here = max_so_far = A[0]
    for x in A[1:]:
        max_ending_here = max(x, max_ending_here + x)
        max_so_far = max(max_so_far, max_ending_here)
    return max_so_far


这种算法稍作修改就可以记录最大子数列的起始位置。 Kadane算法时间复杂度为，空间复杂度为.

因为该算法用到了“最佳子结构”（以每个位置为终点的最大子数列都是基于其前一位置的最大子数列计算得出），该算法可看成动态规划的一个例子。从动态规划的角度看，Base case： 我们首先建立一个与原数列A长度相同的数列dp，dp中的每一个值dp[i]表示以位置i为终点的子数列的最大和。Induction case： 如果以前面一个位置为结束的子数列和为正数，既dp[i-1]>0,那么dp[i]=dp[i-1]+A[i]；否则dp[i]=A[i]。那么dp[n]就是我们想要的该数列的最大连续子数列之和。算法代码如下： 

public int max_subarray(int[] A){
    int[] dp = new int[A.length];
    for(int i=0;i<A.length;i++){
        dp[i]=A[i];
    }
    int max=A[0];
    for(int i=1;i<A.length;i++){
        if(dp[i-1]>0){
            dp[i]=dp[i-1]+A[i];
        }else{
            dp[i]=A[i]
        }
        max=Math.max(max,dp[i]);
    }
    return max;
}

动态规划的时间复杂度、空间复杂度都为

引用

外部链接

取自“https://zh.wikipedia.org/w/index.php?title=最大子数列问题&oldid=32849970”