首页 > 代码库 > Leetcode_num15_Maximun Subarray

Leetcode_num15_Maximun Subarray

题目:Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [?2,1,?3,4,?1,2,1,?5,4],
the contiguous subarray [4,?1,2,1] has the largest sum = 6.

click to show more practice.

More practice:

If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

此题的要求是在给定的数组中找出总和最大的连续数组片段,分别使用o(n)和分而治之的方法。

o(n)的方法比较简单,即是依次遍历数组,记录目前求和值与最大值:若当前数为负数,则计算加上其后的求和值,与最大值进行比较,若大于最大值则更改最大值,其后,将求和值归零,以下一个值为片段的开始;若当前数非负,则只需比较加上其后的求和值与最大值,若求和值大于最大值,则更改最大值。代码如下:

class Solution:
    # @param A, a list of integers
    # @return an integer
    def maxSubArray(self, A):
        L=len(A)
        rs=0
        m=A[0]
        for i in range(0,L):
            rs+=A[i]
            if rs<0:
                if rs>m:
                    m=rs
                rs=0
            else:
                if rs>m:
                    m=rs
            
        return m

divide and conquer的方法,即归并,算法复杂度为o(nlogn),计算式为 T(n)=2*T(n/2)+o(n)

采用递归调用,以数组片段的中间点为分界线,判断该中间点是否包括在最终所求的数组片段内,因此需要比较三个值的大小:包含中间点的最大和值,不包含中间点的最大和值(即左数组片段的最大和值,右数组片段的最大和值),选择其中最大的值作为结果返回。

后两值采用函数递归调用即可得到;

而在求包含中间点的最大和值,需要找到向左延伸的上界和向右延伸的下界。因此,以中间点为起点向左求和,最大值的初始值设为中间点的值,如果当前和值大于最大值,则修改最大值;同理,以中间点右边一点为起点向右求和,最大值的初始值设为该点的值,如果当前和值大于最大值,则修改最大值,将两个最大值相加,即可得到包含中间点的最大和值。具体的代码如下:

class Solution:
    # @param A, a list of integers
    # @return an integer
    def maxSubArray(self, A):
        def maxS(A,left,right):
            if left==right: return A[left]
            middle=(left+right)/2
            leftm=maxS(A,left,middle) 
            rightm=maxS(A,middle+1,right)
            lm=A[middle]
            rm=A[middle+1]
            t=0
            for i in range(middle,left-1,-1):
                t+=A[i]
                if(t>lm):
                    lm=t
            t=0
            for i in range(middle+1,right+1):
                t+=A[i]
                if(t>rm):
                    rm=t
            return max(leftm,rightm,lm+rm)
            
        L=len(A)
        return maxS(A,0,L-1)


Leetcode_num15_Maximun Subarray