最大和サブアレイ - 分裂と征服

Question

私は整数の配列をとり、最大の合計を持つ連続したサブアレイの合計を返す再帰関数を作成しました。

例：

入力：1~4 -9 8 1 3 3 1 -1 -4 -6 2 8 19 -10 -11

サブアレイ：8 1 3 3 1 -1 -4 - 6 2 8 19

合計：34

私のアルゴリズムは少しです。テスト入力の約2/3が間違っています。私のテストのリストはコードの下にあります。

def max_sum_subarray(arr, left, right): 

    maxLeftBorderSum = 0 
    maxRightBorderSum = 0 
    leftBorderSum = 0 
    rightBorderSum = 0 
    center = (left + right)/2 

    if left == right: 
     return arr[left] 

    maxLeftSum = min_sum_subarray(arr, left, center) 
    maxRightSum = min_sum_subarray(arr, center+1, right) 

    for i in range(center, left, -1): 
     leftBorderSum = leftBorderSum + arr[i] 
     if leftBorderSum > maxLeftBorderSum: 
      maxLeftBorderSum = leftBorderSum 

    for i in range(center+1, right): 
     rightBorderSum = rightBorderSum + arr[i] 
     if rightBorderSum > maxRightBorderSum: 
      maxRightBorderSum = rightBorderSum 

    return max(maxLeftBorderSum + maxRightBorderSum, max(maxRightSum, maxLeftSum)) 

一部のテスト：

1 4 -9 8 1 3 3 1 -1 -4 -6 2 8 19 -10 -11 

正解= 34
私の答え= 34

2 9 8 6 5 -11 9 -11 7 5 -1 -8 -3 7 -2 

正解= 30
私の答え= 28

10 -11 -1 -9 33 -45 23 24 -1 -7 -8 19 

解答= 50
私の答え= 47

31 -41 59 26 -53 58 97 -93 -23 84 

解答= 187
私の答え= 187

3 2 1 1 -8 1 1 2 3 

正解= 7
私の答え= 4

12 99 99 -99 -27 0 0 0 -3 10 

Corr電気ショック療法回答= 210
私の答え= 198

-2 1 -3 4 -1 2 1 -5 4 

正解= 6
私の答えは= 6

Answer 1

Diffchecker

#!python3 
def max_sum_subarray(arr, left, right): 

maxLeftBorderSum = 0 
maxRightBorderSum = 0 
leftBorderSum = 0 
rightBorderSum = 0 
center = (left + right)//2 

if left == right: 
    if(arr[left]>0):return arr[left] 
    else:return 0 

maxLeftSum = max_sum_subarray(arr, left, center) 
maxRightSum = max_sum_subarray(arr, center+1, right) 

for i in range(center, left-1, -1): 
    leftBorderSum = leftBorderSum + arr[i] 
    if leftBorderSum > maxLeftBorderSum: 
     maxLeftBorderSum = leftBorderSum 
for i in range(center+1, right+1): 
    rightBorderSum = rightBorderSum + arr[i] 
    if rightBorderSum > maxRightBorderSum: 
     maxRightBorderSum = rightBorderSum 

return max(maxLeftBorderSum + maxRightBorderSum,maxRightSum, maxLeftSum) 

• 基本条件は間違っている
• 用ループ範囲ミス

Answer 2

import sys 
arr = map(int,raw_input().split()) 
def CrossingSum(arr,l,m,h): 
    summ = 0 
    left_sum = -sys.maxint 
    for i in range(m,l-1,-1): 

      summ = summ + arr[i] 
      if summ > left_sum: 
        left_sum = summ 


    summ = 0 
    right_sum = -sys.maxint 
    for i in range(m+1,h+1): 
      summ = summ + arr[i] 
      if summ > right_sum: 
        right_sum = summ 

    return left_sum + right_sum 

def Divide(arr,l,h): 
    if l == h : 
      return arr[l] 
    mid = (l+h)//2 
    maximum = max(Divide(arr,l,mid) , Divide(arr,mid+1,h) , CrossingSum(arr,l,mid,h)) 

    return maximum 

ans = Divide(arr,0,len(arr)-1) 
print "ANSWER IS " , ans