Max Sum Subarray - Divide and Conquer

Question

Я создал рекурсивную функцию, которая принимает в массиве ints и возвращает сумму непрерывного подмассива с наибольшей суммой.

Пример:

вход: 1 4 8 -9 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) 

• Основание условие является неправильным
• для петля диапазон ошибка
• вызова функции неправильно
• если использовать python3 истинное деление

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