Как найти максимальную сумму в массиве питон

Далее мы обсудим алгоритм Кадане в Python и его свойство для решения задачи «Максимальная сумма подмассива». Мы узнаем концепцию алгоритма и поработаем над кодом Python для него, используя пример с соответствующими выходными данными. Наконец, мы обсудим временную сложность алгоритма и реальное применение алгоритма Кадане.

Итак, приступим.

Алгоритм Кадане в Python – это один из популярных подходов, используемых для решения проблемы с помощью динамического программирования. Как мы уже знаем, задача определения максимума подмассива считается одной из популярных задач в области динамического программирования.

Проблема кажется простой, и решением должна быть сумма всех элементов данных в массиве. Однако это не так. Мы также встретим отрицательные целые числа как элементы данных в массиве, которые могут уменьшить сумму всего массива. Таким образом, мы воспользуемся помощью алгоритма Кадане для решения этой проблемы.

Алгоритм Кадане используется для поиска непрерывного подмассива в одномерном целочисленном массиве, который имеет максимально возможную сумму. Основным подходом будет применение метода грубой силы для решения проблемы. Однако при этом временная сложность решения будет O (n ^ 2), что совсем не впечатляет.

Следовательно, мы будем использовать алгоритм Кадане для решения задачи путем обхода всего массива с помощью двух переменных, чтобы отслеживать текущую и максимальную сумму. Наиболее важным аспектом, на который следует обращать внимание при использовании этогои алгоритма, является условие, с помощью которого мы будем обновлять обе переменные.

Понимание алгоритма максимальной суммы подмассива

Давайте теперь рассмотрим основные шаги алгоритма максимальной суммы подмассива, как показано ниже:

1. Шаг 1: мы должны инициализировать max_till_now = 0.
2. Шаг 2: мы должны инициализировать max_ending = 0.
3. Шаг 3: мы должны повторить шаги с 4 по 6 для каждого элемента данных в массиве.
4. Шаг 4. Мы должны установить max_ending = max_ending + a [i].
5. Шаг 5: Если(max_ending <0), мы должны установить max_ending = 0.
6. Шаг 6: Если(max_till_now <max_ending), мы должны установить max_till_now = max_ending.
7. Шаг 7: мы должны вернуть max_till_now.

Мы использовали max_ending для поиска всех положительных элементов данных массива и max_till_now, чтобы найти максимальную сумму элементов данных среди всех положительных сегментов. Таким образом, каждый раз, когда мы получаем положительную сумму при сравнении с max_till_now, мы сможем обновить ее на большую сумму.

Следовательно, всякий раз, когда max_ending становится отрицательным, мы устанавливаем его равным нулю, и для каждой итерации мы будем проверять условие, при котором max_till_now меньше max_ending, чтобы обновить max_till_now, если условие возвращает True.

Использование графического представления в алгоритме Кадане

Давайте рассмотрим следующий пример с целочисленным массивом.

Рис.1: Целочисленный массив.

Рис. 2. Мы инициализируем max_till_now = 0 и max_ending = 0(n = 0).

Рис. 3. Тогда мы получим max_till_now = 0 и max_ending = 0 для n = 1; однако мы получим max_till_now = 4 и max_ending = 4 для n = 2.

Рис. 4. Затем мы присвоим значение n = 3 и 4 и получим max_till_now = 4 и max_ending = 3, а также max_till_now = 4 и max_ending = 1 соответственно.

Рис. 5. Мы получим max_till_now = 6(6> 4) для n = 5 и max_ending = 6.

Рис. 6: Мы также получим max_till_now = 6 и max_ending = 4 для n = 6.

Следовательно, из приведенного выше примера мы найдем максимальный подмассив в диапазоне от n = 2 до n = 5, а максимальная сумма будет равна 6.

Понимание алгоритма Кадане с использованием кода Python

Давайте рассмотрим следующий фрагмент кода, демонстрирующий работу алгоритма Кадане.

Пример:

 
# defining the function to find the maximum subarray sum 
def max_Subarray_Sum(my_array, array_size): 
    # assigning the variables 
    maxTillNow = my_array[0] 
    maxEnding = 0 
     
    # using the for-loop 
    for n in range(0, array_size): 
        maxEnding = maxEnding + my_array[n] 
        # using the if-elif-else statement 
        if maxEnding < 0: 
            maxEnding = 0 
         
        elif(maxTillNow < maxEnding): 
            maxTillNow = maxEnding 
             
    return maxTillNow 
# defining the array 
my_array = [-2, -3, 4, -1, -2, 5, -3] 
# printing the maximum subarray sum for the users 
print("Maximum Subarray Sum:", max_Subarray_Sum(my_array, len(my_array))) 

Выход:

Maximum Subarray Sum: 6 

Объяснение:

В приведенном выше фрагменте кода мы определили функцию как max_Subarray_Sum, принимающую два параметра как my_array и array_sum соответственно. Затем мы присвоили переменной maxTillNow первому значению индекса массива, а maxEnding – нулю. Затем мы использовали цикл for для перебора всего массива.

Мы также использовали условный оператор if-elif-else и возвращаем maxTillNow. Наконец, мы определили массив и распечатали максимальную сумму подмассивов для пользователей, которая в приведенном выше примере равна 6.

Временная сложность

Временная сложность алгоритма Кадана для массива, состоящего из n элементов данных в виде целого числа, определяется как O(n), поскольку в программе должен выполняться только один цикл for. Аналогично, сложность алгоритма во вспомогательном пространстве равна O(1).

Применение

Существуют различные применения алгоритма Кадане, некоторые из которых описаны ниже:

1. Алгоритм Кадане состоит в том, чтобы найти максимальную сумму подмассива для заданного массива целых чисел.
2. Он используется в качестве алгоритма обработки изображений.
3. Его также можно использовать для решения таких задач, как «Station Travel in Order» и «Hostels Along the Coast».
4. Он также используется для бизнес-анализа.

Заключение

Мы можем сделать вывод, что решение не кажется простым при постановке задачи нахождения максимальной суммы подмассива. Однако алгоритм Кадане ее упростил и достиг решения с наименьшими временными сложностями.

Это стало возможным, поскольку алгоритм Кадане использует метод сбора информации, необходимой для достижения решения, избегая нежелательного хранения данных. Следовательно, мы можем рассматривать этот алгоритм как простой пример подхода динамического программирования с множеством практических приложений в реальном мире.

Given lists in a list, find the maximum sum of elements of list in a list of lists. Examples:

Input :  [[1, 2, 3], [4, 5, 6], [10, 11, 12], [7, 8, 9]]
Output : 33 
Explanation: sum of all lists in the given list of lists are:
             list1 = 6, list2 = 15, list3 = 33, list4 = 24 
             so the maximum among these is of 

Input : [[3, 4, 5], [1, 2, 3], [0, 9, 0]]
Output : 12

Method 1 : Traversal of list in lists

We can traverse in the lists inside the list and sum up all the elements in a given list and by max function get the maximum of sum of all elements in lists of list. 

Time Complexity: O(n*m) where n is the number of lists and m is the maximum size of the list.
Auxiliary Space: O(1)

Method 2 : Traversal of list

Traverse in the outer list only, and sum all elements in the inner lists by using sum() function, find the sum of all the lists and get the maximum of all the sum calculated. 

Time Complexity: O(n*m) where n is the number of lists and m is the maximum size of the list.
Auxiliary Space: O(1)

Method 3 : Sum and Max function

sum(max(list1, key=sum))

The above syntax of max() function allows us to find the sum of list in list using the key=sum. max(list1, key=sum), this finds the list with maximum sum of elements and then sum(max(list1, key=sum)) returns us the sum of that list. 

Time Complexity: O(n*m) where n is the number of lists and m is the maximum size of the list.
Auxiliary Space: O(1)

                                                                  Method 4 : Using sum() and sort() methods

Time Complexity : O(NlogN)
Auxiliary Space : O(N)

Method 5 : Using reduce()

This method uses the reduce() function to iterate over the list of lists and a lambda function to compare the sums of each list. The lambda function returns the list with the larger sum, and the reduce function keeps track of the maximum sum by repeatedly applying the lambda function to the list of lists. The final result is the sum of the list with the maximum sum.

Here is another approach using the reduce() function and a lambda function:

Time complexity: O(n*m) where n is the number of lists and m is the maximum size of the list.
Space complexity: O(1)

Last Updated :
11 Jan, 2023

Like Article

Save Article

Представим, что у нас есть список со списками и нам нужно найти вложенный список с максимальной суммой элементов. Задача звучит довольно просто, и решение «в лоб» приходит незамедлительно. Но зачем идти очевидным путём, когда есть более утончённый? Давайте рассмотрим несколько возможных вариантов решения на Python от самого громоздкого до «однострочника».

Способ 1. Обход вложенных списков

Мы можем просто обойти вложенные списки, сложить все элементы в каждом из них и с помощью функции max() найти наибольшую сумму:

def maximum_sum(list_of_lists):
    maxi = 0
 
    # обходим внешний список
    for list in list_of_lists:
        sum = 0
        # обходим вложенные списки
        for item in list:
            sum += item     
        maxi = max(sum, maxi) 
         
    return maxi
     
list_of_lists = [[1, 2, 3], [4, 5, 6], [10, 11, 12], [7, 8, 9]]
print(maximum_sum(list_of_lists)) # выводит 33

Способ 2. Обход внешнего списка

Ещё можно обойти только внешний список и сложить элементы вложенных с помощью функции sum(), а затем найти максимальную сумму с помощью уже знакомой функции max():

def maximum_sum(list_of_lists):
    maxi = 0
    #обходим внешний список
    for l in list_of_lists:
        maxi = max(sum(l), maxi)
         
    return maxi
     
list_of_lists = [[1, 2, 3], [4, 5, 6], [10, 11, 12], [7, 8, 9]]
print(maximum_sum(list_of_lists)) # выводит 33

Способ 3. Функции sum и max

Ещё один способ заключается в сочетании функций sum() и max():

def maximum_sum(list_of_lists):
    return max(sum(l) for l in list_of_lists)
     
list_of_lists = [[1, 2, 3], [4, 5, 6], [10, 11, 12], [7, 8, 9]]
print(maximum_sum(list_of_lists)) # выводит 33

Прим. перев. Кроме того, возможна реализация с помощью параметра key функции max():

def maximum_sum(list_of_lists):
    return sum(max(list_of_lists, key=sum))
     
list_of_lists = [[1, 2, 3], [4, 5, 6], [10, 11, 12], [7, 8, 9]]
print(maximum_sum(list_of_lists)) # выводит 33

Параметр key=sum позволяет найти сумму элементов списка в списке; max(list_of_lists, key=sum) находит список с максимальной суммой элементов, а sum(max(list_of_lists, key=sum)) возвращает сумму элементов этого списка.

Перевод статьи «Python | Maximum sum of elements of list in a list of lists»

Дан целочисленный массив, найдите в нем непрерывный подмассив с наибольшей суммой.

Например,

Потренируйтесь в этой проблеме

Задача отличается от задачи нахождения подпоследовательности максимальной суммы. В отличие от подпоследовательностей, подмассивы должны занимать последовательные позиции в исходном массиве.

 
Мы можем легко решить эту задачу за линейное время, используя Алгоритм Кадане. Идея состоит в том, чтобы поддерживать максимальный (с положительной суммой) подмассив, “заканчивающийся” на каждом индексе данного массива. Этот подмассив либо пуст (в этом случае его сумма равна нулю), либо состоит на один элемент больше, чем максимальный подмассив, оканчивающийся на предыдущем индексе.

Алгоритм может быть реализован следующим образом на C++, Java и Python:

Временная сложность приведенного выше решения равна O(n) и не требует дополнительного места, где n это размер ввода.
 

 
Приведенный выше код не обрабатывает случай, когда все элементы массива отрицательные. Если массив содержит все отрицательные значения, ответом является максимальный элемент. Мы можем легко разместить эту проверку перед тем, как продолжить алгоритм. Реализацию можно увидеть ниже на C++, Java и Python:

Этот подход требует двух обходов входного массива. Мы можем легко модифицировать основной алгоритм, чтобы он обрабатывал и отрицательные целые числа. Алгоритм может быть реализован следующим образом на C++, Java и Python:

Из-за того, как этот алгоритм использует оптимальные основания (максимальный подмассив, заканчивающийся в каждой позиции, вычисляется просто из связанной, но меньшей и перекрывающейся подзадачи: максимальный подмассив, заканчивающийся в предыдущей позиции), этот алгоритм можно рассматривать как простой пример динамическое программирование.

 
Связанный пост:

Вывести непрерывный подмассив с максимальной суммой

 
Использованная литература: https://en.wikipedia.org/wiki/Maximum_subarray_problem

Реализации Python и javascript для алгоритмов

Постановка проблемы

У вас есть массив из n чисел. Вам нужно найти наибольшую сумму последовательных чисел массива.

По сути, это поиск подмассива с наибольшей суммой.

Например, массив [1, 2, 3, 4] будет иметь наибольшую сумму = 10, которая является суммой массива в целом. Для массивов без отрицательных целых чисел максимальная сумма подмассива равна сумме самого массива.

Теперь, что происходит, когда у вас есть отрицательные целые числа?

Возьмите массив [-1, -3, 4, 2], где подмассив с максимальной суммой будет [4, 2] с суммой = 6.

Что происходит, когда у вас есть огромный массив? Как разработать алгоритм для решения этой проблемы?

Решение

На самом деле есть много разных способов сделать это. Позвольте мне логически разбить два подхода, чтобы помочь вам понять процесс мышления.

Решение 1

Очень прямой подход, о котором мы можем думать, может выглядеть следующим образом:

• Мы создаем все возможные подмассивы из основного массива.
• Затем мы проверяем сумму каждого подмассива и возвращаем максимальную сумму.

Довольно просто? Давайте сделаем пробный прогон, чтобы понять это лучше.

• Пусть массив будет [-1, 2, -5, 7]
• Чтобы создать все подмассивы этого массива, мы можем выбрать каждый элемент и создать подмассив со всеми остальными элементами в последовательности.
• Вот подмассивы- [-1], [-1, 2], [-1, -5], [-1, 7], [-1, 2, -5], [-1, 2, 7], [-1, -5, 7], [-1, 2, -5, 7], [2], [2, -5], [2, 7], [2, -5, 7], [-5], [-5, 7], [7]. Ах, очень утомительный процесс.
• С каждым созданным нами подмассивом мы можем проверить сумму и сохранить ее запись.
• Всякий раз, когда сумма превышает нашу предыдущую запись, мы обновляем значение.
• Как только мы пройдемся по всем подмассивам, записанная нами сумма будет искомым ответом.
• Если мы посмотрим на все подмассивы, то заметим, что [7, 2]имеет максимальную сумму, которая равна 9.

Давайте попробуем сделать это на двух разных языках программирования. Идея состоит не только в том, чтобы решить проблему, но и в том, чтобы изучить синтаксис и код Python и JavaScript. Я предполагаю, что у вас есть общее представление о том, как писать код: циклы for, операторы if-else, объявление переменных и использование функций. Если нет, ознакомьтесь с этими вещами, прежде чем читать код.

У нас слишком много циклов for, а это значит, что временная сложность — это плохо. В данном случае это O(n³), потому что нам нужно выполнить три цикла.

Решение 2

Чтобы сделать вещи эффективными в таких задачах, нам нужно подумать о способах уменьшить количество циклов.

Есть ли способ решить это с помощью одного цикла?

Должен быть какой-то трюк, который мы можем использовать, чтобы сделать это. Посмотрим, сможем ли мы построить мыслительный процесс.

• Если мы перебираем массив только один раз, это означает, что мы посещаем каждый элемент массива один раз.
• Давайте теперь соединим точки в обратном порядке. Чтобы найти наш ответ, нам нужно сначала найти подмассив, который будет иметь максимальную сумму.
• Нам обязательно нужно посетить каждый элемент один раз. Что вы можете сказать об этом элементе по отношению к подмассиву с максимальной суммой? Он либо принадлежит этому подмассиву, либо нет. Правильно?
• Если он принадлежит подмассиву с максимальной суммой, вы можете добавить его значение во временную переменную, где вы сохраняете и постоянно обновляете потенциальную максимальную сумму. Если это не так, вы можете просто проигнорировать его и перейти к следующему элементу.
• Если вы сделаете это по всему массиву, что вы получите? Сумма всех элементов, принадлежащих подмассиву с максимальной суммой = ответ, который мы ищем, и мы получаем его, запустив всего один цикл!
• Теперь у вас возникнет вопрос: как мы узнаем, что данный элемент принадлежит этому подмассиву?
• Предположим, что у нас есть массив из n элементов. Мы находимся в k-м элементе этого массива.
• Если этот k-й элемент является частью нашего максимального подмассива, что в нем будет особенного? Либо она будет больше, чем сумма элементов до k-1, либо максимальная сумма до k-1 + kth элемента будет больше.
• Вы заметили, как мы создаем подзадачу с помощью нашей логики?
• Максимальная сумма подмассива для этого массива, заканчивающегося k-м элементом, фактически является максимальной суммой подмассива массива до k-1-го элемента + k-го элемента (если k-й элемент положителен).
• В любой момент времени мы находим максимальную сумму подмассива для массива до k-го элемента. Когда мы достигнем n-го элемента, мы бы нашли ответ для всего массива.

Звучит запутанно? Ничего страшного. Если вы впервые сталкиваетесь с такой проблемой, это может быть немного сложно. Давайте сделаем пробный прогон с реальным массивом.

• Пусть массив равен [-1, 2, -5, 7], как в примере, который мы использовали в решении 1. Итак, нам нужно собрать сумму элементов, принадлежащих подмассиву с максимальной суммой (назовем его нашим целевым подмассивом).
• Мы запускаем только один цикл. Итак, сначала мы идем к -1, и это сам по себе подмассив с суммой = -1. Предположим, что -1 является частью нашего целевого подмассива. -1 теперь наша временная максимальная сумма.
• Далее идем к 2. Теперь он либо является частью нашего целевого подмассива, либо нет. Откуда мы это знаем? Если он является частью подмассива, он должен быть либо больше текущей максимальной суммы, либо должен быть добавлен к максимальной сумме. 2 > -1 + 2 = 1, что больше, чем наша текущая временная максимальная сумма. Итак, давайте обновим нашу временную максимальную сумму = 2. Это просто подтверждает, что наше предыдущее предположение о том, что -1 является частью целевого массива, неверно. Теперь предположим, что 2 является частью целевого массива.
• Давайте перейдем к следующему элементу, то есть -5. -5 явно меньше текущей максимальной суммы, которую мы имеем. Таким образом, мы можем игнорировать его и перейти к следующему элементу.
• Теперь давайте перейдем к следующему элементу, 7, который больше, чем текущая максимальная сумма = 2. 7 + 2 = 9, что также больше, чем наша текущая максимальная сумма. Это означает, что 7 является частью нашего целевого подмассива, и мы можем обновить нашу максимальную сумму = 9.
• Мы достигли конца массива, и решение, к которому мы пришли, это 9, что является требуемым ответом, и мы только что использовали один цикл!

Короче говоря, мы подошли к каждому элементу массива и проверили, будет ли он частью подмассива с максимальной суммой. Если это так, мы просто добавляем его в нашу переменную maxSum и переходим к следующему элементу.

В конце мы получим требуемый ответ.

Вот реализация кода в javascript и python для этого подхода:

Поскольку мы используем только один цикл, временная сложность равна O(n).

Некоторые наблюдения

• Я запустил обе эти программы в Leetcode для соответствующего вопроса (решение 2).
• Программа javascript выполнялась меньше времени, чем код python.
• Однако python занимал меньше памяти, чем javascript.

Ключевые выводы

• Если вы столкнетесь с похожей проблемой на собеседовании, подумайте о том, как вы пытаетесь найти решение.
• Возьмите образец тестового примера и выполните пробный прогон, как я сделал здесь в первую очередь.
• И после этого вы можете кодировать его.
• Если вы столкнулись с такой проблемой в онлайн-тестировании, использование javascript вместо python может помочь вам занять более высокое место в рейтинге, поскольку он быстрее.
• Когда вы имеете дело с массивами и замечаете, что вам нужно выполнить итерацию по массиву, вам следует подумать об использовании наименьшего количества циклов for.
• Оттуда подумайте о том, что вы можете сделать, как вы можете отслеживать полезную информацию, проходя через каждый элемент массива.
• В таких задачах мы обычно хотели бы отслеживать две переменные: текущее значение, которое мы вычисляем на каждой итерации, и максимальное или минимальное значение, которое будет окончательным ответом, который постоянно обновляется по мере прохождения массива.

Fundamental Approach: A summary.
1. Have a single for loop.
2. Calculate a currentValue for each element in the array based on the question.
3. Then update the maxValue as max(maxValue, currentValue)
4. Vice-versa for minValue.

Попробуйте решить этот вопрос Leetcode самостоятельно, не видя никаких ссылок после прочтения этой статьи, и проверьте свое понимание.

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