【算导】分治法求解最大子数组

任意子数组必然是以下三种情况之一:

1.完全在a[low...mid]中。

2.完全在a[mid+1...high]中。

3.跨越了数组中点。

若结果为1或2,则可通过递归求解,若结果为3,则可通过一个线性时间复杂度的函数求解:

FIND-CROSS(a,low,mid,high)
    leftsum=0;
    sum=0;
    for(int i=mid;i>=low;i--)
    {
        sum+=a[i];
        leftsum=max(leftsum,sum);
    }
    rightsum=0;
    sum=0;
    for(int i=mid;i<high;i++)
    {
        sum+=a[i];
        rightsum=max(rightsum,sum);
    }
return leftsum+rightsum

最后写一个总函数:

FIND(a,low,high)
    if(low==high)
        return a[low]
    else
    {
        mid=(low+high)/2
        b=FIND(a,low,mid)
        c=FIND(a,mid+1,high)
        d=FIND-CROSS(a,low,mid,high)
        return max(b,c,d);
    }

时间复杂度O(nlogn)

一个更优化的方法,时间复杂度O(n)
从头遍历,每遍历一个数,加到sum中,与当前最大值res比较更新res,当sum小于0时,sum、
等于0,相当于把之前的所有结果清零,从下一个数重新比较并继续更新res

int maxSubArray(vector<int> nums) {
    int ge = nums.size();
    if (ge == 0)
        return 0;
    int sum = 0;
    int res = nums[0];
    for (int i = 0; i < ge; i++)
    {
        sum += nums[i];
        res = max(sum, res);
        if (sum < 0)
            sum = 0;        
    }
    return res;
}
最后编辑于 :
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

友情链接更多精彩内容