Как найти наибольшую сумму последовательных членов последовательности из n положительных и отрицательных чисел?

Question

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

[1, -3, 4, -7, 8] -> самая крупная сумма должна быть 8. (Сумма сама по себе)

[5,5, -3,6, - 10] -> самая крупная сумма должна быть 5 + 5 + (-3) + 6 = 13

[3, -9, 10, 5] -> самая крупная сумма составляет 10 + 5 = 15

def find_max(seq): 
    if len(seq) == 1: 
     if(seq[0] > sum): 
      sum = seq[0] 
     return seq 
    else: 
     mid = len(seq)//2 
     left = [:seq] 
     right = [seq:] 
     find_max(left) 
     find_max(right) 

Answer 1

Я не уверен, что этот ответ будет полезен, поскольку я понимаю, что ваш вопрос касается не самого алгоритма, а того, как реализовать его с помощью Python (и я не знаю Python). Но есть еще один алгоритм, который вы могли бы использовать, возможно, вы можете реализовать, не спрашивая никакой помощи. Обратите внимание, что этот алгоритм вычисляет только сумму, а не последовательность, которая отбирает эту сумму (насколько я понимаю, это то, что вы хотите). Вот C-образное псевдокодное решение:

int findMax(sequence, length) { 

    int maxSumStartingAt[length]; 
    maxSumStartingAt[length - 1] = sequence[length-1]; 

    for(int i=length-2; i >= 0; i--) { 
     int tempSum = sequence[i] + maxSumStartingAt[i+1]; 
     if (sequence[i] > tempSum) { 
      maxSumStartingAt[i] = sequence[i]; 
     } else { 
      maxSumStartingAt[i] = tempSum; 
     } 
    } 

    int maxSum = maxSumStartingAt[0]; 
    for(int i = 1; i < length; i++) { 
     if (maxSum < maxSumStartingAt[i]) { 
      maxSum = maxSumStartingAt[i]; 
     } 
    } 

    return maxSum; 
} 

Теперь я объясню вам, как это решение работает.

1) Поскольку подпоследовательность, которая дает наибольшую сумму, должна начинаться с некоторого индекса i, идея состоит в том, чтобы вычислить для каждого индекса i наибольшую сумму последовательных элементов, начиная с i. Результатом является максимум между этими суммами.

2) Теперь, если кто-то сказал вам, что подпоследовательность элементов, которая дает наибольшую сумму, начинается с индекса i и что наибольшая сумма последовательных элементов для подпоследовательности, начинающейся с индекса i + 1, равна x, как бы вы могли вычислить желаемую сумму? Было бы просто максимум между

sequence[i] 

и

sequence[i] + x 

Мы можем использовать эту информацию, чтобы вычислить самую большую сумму, начиная с индекса I для каждого индекса я: Начнем с последнего элемента последовательности ака

sequence[length-1] 

если мы начинаем индексацию от 0. Что такое крупная сумма, начиная с этого индекса, который я буду называть maxSumStartingAt [длина-1]? Это не может быть иной, как

sequence[length - 1] 

сам по себе, так как это представляет собой последовательность 1-элемент. И какова самая большая сумма, начиная с длины индекса - 2? Это максимум между

sequence[length-2] 

и

sequence[length-2] + maxSumStartingAt[length-1] 

А что начинается самая крупная сумма по длине указательного - 3?Опять же, это максимум между

sequence[length-3] 

и

sequence[length-3] + maxSumStartingAt[length-2] 

Мы можем применить эту формулу к каждому индексу последовательности, и в конце концов мы получаем индекс 0, и мы имеем самую большую сумму, начинающуюся в родовом индекс i для каждого индекса. Это именно то, что делает первый цикл в решении. На этом этапе все, что нам нужно сделать, это найти максимум между всеми вычисленными суммами (это то, что делает второй для цикла в решении). Этот максимум является результатом.

Одна нота на вашем решении. Учитывая, что я не знаю Python, поэтому я не могу судить о коде, который вы опубликовали, если он делает именно то, что вы заявили в вопросе (т. Е. Разбивая последовательность на две половины и вычисляя наибольшую сумму для каждой половины, а затем возвращая максимум между этими двумя значениями) он не работает, поскольку он не охватывает случай, когда наибольшая сумма получается последовательностью, которая охватывает две половины.

Answer 2

def largestSum(arr): 
    curr = arr[0] 
    lsum = arr[0] 

    if len(arr) <= 1: 
    return arr 

    for i in range(1, len(arr)): 
    curr = max(arr[i], curr + arr[i]) 

    if curr > lsum: 
     lsum = curr 
    return lsum 

largestSum([-2,3,2,-1])