Массивы питон максимальная сумма

Python: максимальная сумма подмассива

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

def maxSequence(arr): #Latest attempt, some issue. old_arr = [] print(arr) while old_arr != arr: old_arr = arr if arr[0] > 0 and arr[len(arr)-1] > 0: #For when both sides are positive, need to be sure there is not anything to be gained by eliminating some side section new_sum = 0 y=0 while new_sum >= 0 and y != -1: new_sum = sum(arr[:y]) y=y+1 if y == len(arr)-1: y=-1 if y != -1: arr = arr[y-1:] print("left %s" %(new_sum)) print("left %s" % (arr)) new_sum = 0 y = 0 while new_sum >= 0 and y != -1: new_sum=sum(arr[(len(arr)-y):]) y=y+1 if y == len(arr)-1: y=-1 if y != -1: arr = arr[:len(arr)-y+1] print("right %s" %(new_sum)) print("right %s" % (arr)) else: while arr[0] < 0 or arr[len(arr)-1] < 0: #To eliminate negatives on sides if arr[0] < 0: arr = arr[1:] if arr[len(arr)-1] < 0: arr = arr[:len(arr)-1] print("negative %s" % (arr)) print(arr) print(sum(arr)) 

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

Это не дает правильный результат 105, когда дан список

[26, -25, -23, -2, 3, -6, -5, 15, 7, 8, 17, 15, 29, -2, 16, -25, -8, -25, -27, 15, -29, -11, -12, 1, -14, 21, 20, 30, -29, 17, 9, -19, 28, 11, 6, -10, -25, 27, -18, 6, -13, -13, 25, -22, 8, 9, -4, -25, 17, -26] 

В итоге получается сумма 94, сократив список до

[21, 20, 30, -29, 17, 9, -19, 28, 11, 6] 

Извините за длинный пост, но я просто не могу понять, что я делаю неправильно. Заранее спасибо за помощь!

Вот результат, когда вышеупомянутый список предоставляется в качестве входных данных, я прошел и рассмотрел каждый шаг, и каждое исключение из списка кажется мне логичным, я не знаю, как можно получить конечную сумму 105. Если бы кто-нибудь мог помочь мне понять, я был бы очень признателен!

[26, -25, -23, -2, 3, -6, -5, 15, 7, 8, 17, 15, 29, -2, 16, -25, -8, -25, -27, 15, -29, -11, -12, 1, -14, 21, 20, 30, -29, 17, 9, -19, 28, 11, 6, -10, -25, 27, -18, 6, -13, -13, 25, -22, 8, 9, -4, -25, 17, -26] negative [26, -25, -23, -2, 3, -6, -5, 15, 7, 8, 17, 15, 29, -2, 16, -25, -8, -25, -27, 15, -29, -11, -12, 1, -14, 21, 20, 30, -29, 17, 9, -19, 28, 11, 6, -10, -25, 27, -18, 6, -13, -13, 25, -22, 8, 9, -4, -25, 17] left -22 left [-2, 3, -6, -5, 15, 7, 8, 17, 15, 29, -2, 16, -25, -8, -25, -27, 15, -29, -11, -12, 1, -14, 21, 20, 30, -29, 17, 9, -19, 28, 11, 6, -10, -25, 27, -18, 6, -13, -13, 25, -22, 8, 9, -4, -25, 17] right -8 right [-2, 3, -6, -5, 15, 7, 8, 17, 15, 29, -2, 16, -25, -8, -25, -27, 15, -29, -11, -12, 1, -14, 21, 20, 30, -29, 17, 9, -19, 28, 11, 6, -10, -25, 27, -18, 6, -13, -13, 25, -22, 8, 9, -4] negative [3, -6, -5, 15, 7, 8, 17, 15, 29, -2, 16, -25, -8, -25, -27, 15, -29, -11, -12, 1, -14, 21, 20, 30, -29, 17, 9, -19, 28, 11, 6, -10, -25, 27, -18, 6, -13, -13, 25, -22, 8, 9] left -3 left [-5, 15, 7, 8, 17, 15, 29, -2, 16, -25, -8, -25, -27, 15, -29, -11, -12, 1, -14, 21, 20, 30, -29, 17, 9, -19, 28, 11, 6, -10, -25, 27, -18, 6, -13, -13, 25, -22, 8, 9] right -5 right [-5, 15, 7, 8, 17, 15, 29, -2, 16, -25, -8, -25, -27, 15, -29, -11, -12, 1, -14, 21, 20, 30, -29, 17, 9, -19, 28, 11, 6, -10, -25, 27, -18, 6, -13, -13, 25] negative [15, 7, 8, 17, 15, 29, -2, 16, -25, -8, -25, -27, 15, -29, -11, -12, 1, -14, 21, 20, 30, -29, 17, 9, -19, 28, 11, 6, -10, -25, 27, -18, 6, -13, -13, 25] left -5 left [-12, 1, -14, 21, 20, 30, -29, 17, 9, -19, 28, 11, 6, -10, -25, 27, -18, 6, -13, -13, 25] right -1 right [-12, 1, -14, 21, 20, 30, -29, 17, 9, -19, 28, 11, 6, -10, -25, 27, -18, 6] negative [1, -14, 21, 20, 30, -29, 17, 9, -19, 28, 11, 6, -10, -25, 27, -18, 6] left -13 left [21, 20, 30, -29, 17, 9, -19, 28, 11, 6, -10, -25, 27, -18, 6] right -12 right [21, 20, 30, -29, 17, 9, -19, 28, 11, 6, -10, -25, 27] left 84 left [21, 20, 30, -29, 17, 9, -19, 28, 11, 6, -10, -25, 27] right -8 right [21, 20, 30, -29, 17, 9, -19, 28, 11, 6] left 77 left [21, 20, 30, -29, 17, 9, -19, 28, 11, 6] right 53 right [21, 20, 30, -29, 17, 9, -19, 28, 11, 6] [21, 20, 30, -29, 17, 9, -19, 28, 11, 6] 94 

Источник

Алгоритм Кадане в Python – пример использования

Далее мы обсудим алгоритм Кадане в Python и его свойство для решения задачи «Максимальная сумма подмассива». Мы узнаем концепцию алгоритма и поработаем над кодом 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
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)))

В приведенном выше фрагменте кода мы определили функцию как 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. Он также используется для бизнес-анализа.

Заключение

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

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

Источник

Задача на поиск списка с максимальной суммой элементов

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

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)) возвращает сумму элементов этого списка.

Что думаете?

Прочитал статью, глянул список вакансий, а там из связанного с IT, разве что PM. Статье 2 дня, неужели за 2 дня успели найти "нормальных мидлов"?)Что-то не сходится.

К слову сказать, моя гештальт-психотерапевт помогла это отработать, по крайне мере, убрать пиковые проявления. Чувство, что "я недо" до сих пор проскакивает, но теперь его легче сразу осознать и не дать этой мысли развиться. Так что синдром самозванца поправим)

Вот про парную работу людей, которые знают разные системы сайта: в точку. В моем случае один питонист, а второй хорошо знает систему продаж, вместе получается писать кастомную аналитику продаж для Google Looker. По отдельности каждый укатывается в глубокие затыки, как оказалось. Так что синергия – сила!Интересно, что джунов и мидлов можно в пару ставить, а вот двух сеньоров – уже не стоит. Что это: неизбежный рост самомнения?

Источник