Maximum Subarray Leetcode Python

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.
この問題は3つの方法で解くことができる.
1つ目はbrute forceの方法でarray全体を両側に循環させることです.最大値を取得します.
ここで空間O(1)
時間O(n^2)

def brutef(arr):
    maxval=-10000
    
    for i in range(len(arr)):
        for j in range(i,len(arr)):
            if maxval<sum(arr[i:j]):
                print i,j
                maxval=max(maxval,sum(arr[i:j]))
                result=arr[i:j]
    

第2のmergesortの思想を借りて、array全体を順次下に分けてそれぞれ左に右に最大を探して、最後に最大の合併をします.
毎回2つに分かれているので、時間の複雑さはO(nlog)
まず関数を定義するのはdivideconが各ステップの最適化を求めるために使用することです

def dividecon(num,low,mid,high):
    #calculate left
    lowsum=-10000
    cursum=num[low]
    left=low
    for index in reversed(range(low,mid)):
        cursum+=num[index]
        if cursum>lowsum:
            lowsum=cursum
            left=index
    highsum=-10000
    cursum=0
    right=high
    for index in range(mid+1,high):
        cursum+=num[index]
        if cursum>highsum:
            highsum=cursum
            right=index
    return [left,right,lowsum+highsum]

は、メイン関数でこの関数を呼び出します.

def findsub(A,low,high):
    if high==low:
        return [low,high,A[low]]
    else:
        mid=low+(high-low)/2
        [leftlow,lefthigh,leftsum]=findsub(A,low,mid)
        [rightlow,righthigh,rightsum]=findsub(A,mid+1,high)
        [crosslow,crosshigh,crosssum]=dividecon(A,low,mid,high)

        if leftsum>=rightsum and leftsum>=crosssum:
            return [leftlow,lefthigh,leftsum]

        if rightsum>=leftsum and rightsum>=crosssum:
            return [rightlow,righthigh,rightsum]
        else:
            return [crosslow,crosshigh,crosssum]

最大が左にある場合は左の値を返し、最大が右にある場合は右の値を返します.そうしないと、両者が交差してcrossの値を返します.
もう1つの方法は時間O(n)空間O(1)である.
方法はarray全体をスキャンして現在の最大値を記録し、得られた現在値が0未満であれば0にし、最後に答えを得ることです.

def findmax(arr):
    cursum=0
    maxval=arr[0]
    for index in range(len(arr)):
        if cursum<0:
            cursum=0
        cursum+=arr[index]
        maxval=max(maxval,cursum)