最大子数组问题

2017-03-12

基本策略

分治策略

基本思想

取中点，具有最大和的连续子数组必在

完全在中点左边
跨过中点
完全在中点右边

代码

var INT_MIN = 0;
/**
 * [cross_middle 跨中点时计算最大和]
 * @Author   etoile
 * @DateTime 2017-03-12T18:21:03+0800
 * @param    {[type]}                 arr [传入数组]
 * @param    {[type]}                 l   [左下标]
 * @param    {[type]}                 m   [中间值]
 * @param    {[type]}                 r   [右下标]
 * @return   {[type]}                     [description]
 */
function cross_middle(arr,l,m,r){
    var i,
        sum=0,
        l_max=INT_MIN,
        r_max=INT_MIN;
    for(i=m;i>=l;i--){
        sum+=arr[i];
        if(sum > l_max) l_max=sum;
    }
    sum=0;
    for(i=m+1;i<=r;i++){
        sum+=arr[i];
        if(sum>r_max) r_max=sum;
    }
    return (l_max+r_max);
}

/**
 * [maxsubset 递归运算，求出最大值]
 * @Author   etoile
 * @DateTime 2017-03-12T18:22:47+0800
 * @param    {[type]}                 arr [传入数组]
 * @param    {[type]}                 l   [左下标]
 * @param    {[type]}                 r   [右下标]
 * @return   {[type]}                     [description]
 */
function maxsubset(arr,l,r){
    // 测试基本情况，即数组中仅有一个元素
    if(l == r) return arr[l];
    // 保护
    if(l>r){
        return 0;
    }
    // 划分子数组，计算中点下标mid
    var m= parseInt((l+r)/2),
        l_max=INT_MIN,
        r_max=INT_MIN,
        c_max=INT_MIN;
    // 子数组中至少包含两个元素，递归求解左右子数组中的最大子数组
    l_max=maxsubset(arr,l,m);
    r_max=maxsubset(arr,m+1,r);
    c_max=cross_middle(arr,l,m,r);
    if(l_max >= r_max&&l_max >= c_max) return l_max;
    else if(r_max >= l_max&&r_max >= c_max) return r_max;
    else return c_max;
}

注意

这个代码是在之前看到的一个C代码上改的，JS中遇到除法一定要格外当心，记得转类型。