Есть ли какой-нибудь алгоритм, сложность времени которого O (n ^ 3) для списка максимальной суммы?

Question

Когда я читаю ответ на предыдущий вопрос ! при переполнении стека было сказано, что можно решить максимальный суммарный подсписок для O (n).

И я также написал код, вычислительная сложность которого была O (n ^ 2).

Тем не менее, я слышал, что существует алгоритм для определения максимального списка для O (n ^ 3).

Если вы это знаете, я был бы признателен, если бы вы поделились этим со мной.

Код для O (n)

def mssl(l):
    best = cur = 0
    for i in l:
        cur = max(cur + i, 0)
        best = max(best, cur)
    return best

Код для O (n ^ 2)

def solution(A):
    start = None
    end = None
    max_total = 0

    for i in range(len(A)):
        for j in range(i, len(A)):
            tmp = sum(A[i:j+1])
            if max_total < tmp:
                max_total = tmp
                start = i
                end = j

    return max_total, start, end


if __name__ == '__main__':
    A = [18, -10, 30, 23, -26]
    ans = solution(A)
    print(ans)

Я хотел бы знать любой алгоритм для решения Максимального Сумма Подсписок для O (n ^ 3).

Answer 1

A[i:j+1]

Эта часть копирует j + 1 - i элементов.

for j in range(i, len(A)):

Сумма j + 1 - i для j от i до n - 1 (n = len(A)) включительно:

• сумма j в том же диапазоне, что
  • сумма j для j от 1 до n - 1: (n - 1) n / 2 = n² / 2 - n / 2
  • минус сумма j для j от 1 до i - 1: (i - 1) i / 2 = i² / 2 - i / 2
• плюс сумма 1 в том же диапазоне, которая равна 1 (n - i) = n - i
• плюс сумма −i в том же диапазоне, которая равна −i (n - i) = −in + i²

Соберите все вместе, и вы получите n² / 2 - n / 2 + i² / 2 - i / 2 + n - i - in + i² = n² / 2 + n / 2 + 3/2 i² - (n + 3/2) i копий для петли j.

for i in range(len(A)):

Сумма n² / 2 + n / 2 + 3/2 i² - (n + 3/2) i для i от 0 до l - 1 составляет:

• сумма n² / 2 + n / 2: (n² / 2 + n / 2) n = n³ / 2 + n² / 2
• плюс 3/2 сумма i² : 3/2 (n - 1) (n - 1 + 1) (2 (n - 1) + 1) / 6 = (n - 1 ) (n) (2n + 1) / 4 = n / 4 (2n² - 2i + n - 1) = n³ / 2 - n² / 4 - n / 4
• минус (n + 3/2), умноженное на сумму i: (n + 3/2) (n - 1) n / 2 = (n² + 3/2 n - n - 3/2) n / 2 = n³ / 2 + n² / 4 - 3n / 4

, что составляет n³ / 2 + n² / 2 + n³ / 2 - n² / 4 - n / 4 - n³ / 2 - n² / 4 + 3n / 4 = n³ / 2 + n / 2 копии , для типичного измерения сложности времени O (n ^ 3), а не O (n ^ 2).

(Проверка работоспособности: n³ + n / 2 - это всегда целое число.)