Подмассив максимальной суммы - разделяй и властвуй

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

Пример:

ввод: 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

Правильный ответ = 210
Мой ответ = 198

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

Правильный ответ = 6
Мой ответ = 6


python recursion algorithm divide-and-conquer
person user3612719    schedule 23.01.2017    source источник

Ответы (2)


arrow_upward
2
arrow_downward

Проверка различий

#!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 использует истинное деление
person Smart Manoj    schedule 23.01.2017
comment
Какая интуиция стоит за переходом от center к left? for i in range(center, left-1, -1): ... - person Brayoni; 27.05.2020

arrow_upward

arrow_downward

person    schedule
comment
Добро пожаловать в StackOverflow! Вы должны учитывать, что обычно лучше объяснить, что вы сделали здесь и почему. - person Leontyev Georgiy; 26.10.2017