def maxsub(a,N):
max_so_far = a[0]
curr_max = a[0]
for i in range(1,N):
curr_max = max(a[i], curr_max + a[i])
max_so_far = max(max_so_far,curr_max)
return max_so_far
N = int(input())
arr = [int(input()) for _ in range(N)]
if all(x > 0 for x in arr) == True:
print(sum(arr) - max(arr))
else:
print(maxsub(arr,N))
Этот код помогает найти максимальную сумму любого подмассива, но мне нужно найти, какая максимальная сумма подмассива ›будет, если мне придется удалить в нем самый большой элемент.
Например,
Если у нас есть 7 элементов в массиве как [0, -11,5,5, -10,0,50], максимальная сумма подмассива, если нам нужно удалить его самый большой элемент ‘будет 5
Для 5 элементов [-2,10, -2,10,6] ответ будет 14 < / strong>
Что мне здесь делать?
Похоже на проблему конкуренции — не могли бы вы дать ссылку на источник? Также насколько быстро приемлемо? — person keancodeup schedule 09.05.2021
Другой подход мог бы быть:
Помните, что производительность этого алгоритма может отличаться от такового в результате более явного индексирования, если вы имеете дело с большими массивами.
Приведенный выше код можно сжать до:
ИЗМЕНИТЬ ————————————
если производительность является ключевым фактором, сначала подумайте о том, чтобы запрограммировать ее на другом языке. Если вам нужно придерживаться Python, вы можете попробовать:
Что такое N и зачем он нужен? — person keancodeup; 10.05.2021
N — максимальный размер подмассива. Я не знаю, зачем это нужно, но он был использован в вопросе, поэтому я просто сохранил это требование. — person keancodeup; 10.05.2021
maxsub3([-10, 7, -4, 1, 5], 5)
, похоже, возвращает(1, 8)
. Я думаю, что правильный результат будет(2, 9)
. — person keancodeup; 10.05.2021Простите, вы правы. Это должно быть
for j in range(i+2,LastInd):
. Исправляю свой ответ — person keancodeup; 11.05.2021Вот код.
max_finder()
возвращает максимальную сумму, начальный и конечный индексы. Я реализовал его, следуяKadane's Algorithm
описанному здесьЭто не удается в таких случаях, как
[5, -100, 1, 1]
, потому что его заманивает большая пятерка, которая затем исчезает. — person keancodeup; 09.05.2021Да, мне кажется, правильно, я понимаю, о чем говорит @j_random_hacker. заботиться о разработке? — person keancodeup; 09.05.2021
Извините, попробуйте вместо этого
[1, 1, -100, 5]
. (В вашемmax_finder()
есть ошибка:max_finder([5, -100, 1, 1])
должно быть(5, 0, 0)
, но он неправильно возвращает(2, 2, 3)
. В примерах входных данных, которые я дал обоим, есть подмассивы с суммой 5.) — person keancodeup; 10.05.2021мои извинения @j_random_hacker, это было неверно при первом вводе, и я не заметил. Я соответствующим образом отредактирую функцию. Спасибо. — person keancodeup; 10.05.2021
Нет проблем, но более серьезная проблема заключается в том, что теперь, когда
max_finder()
правильно находит интервал максимальной суммы, оба моих примеров ввода дают окончательный ответ 0, когда правильный ответ равен 1. — person keancodeup; 10.05.2021Возьмем пример [5, -100, 1, 1]. Максимальный интервал составляет [0: 1], то есть только первый индекс. тогда, когда мы вычитаем максимальное значение в пределах этого интервала из максимальной суммы, становится понятно, почему мой ответ равен 0. Можете ли вы объяснить, почему правильным ответом будет 1? ты — person keancodeup; 10.05.2021
Вопрос заключается в том, чтобы указать максимальное значение, которое можно получить, взяв все элементы в интервале, удалив самый большой и просуммировав остальные. Если вы возьмете интервал
[1, 1]
и удалите самый большой элемент (один из1
s) и просуммируете остальные, вы получите 1. — person keancodeup; 10.05.2021Давайте продолжим это обсуждение в чате. — person keancodeup; 10.05.2021
Вот повторение, которое кажется довольно быстрым для случайных данных, но более медленным с сильно отсортированными данными). С 3000 элементов это кажется примерно в 10-20 раз быстрее, чем maxsub3 (для случайных, не отсортированных данных). Ответ также включает тесты точности против грубой силы. Повторение наивно — некоторые из обратных прогонов могли найти лучшее решение на основе порогового значения
max_subarray
.Пусть
f(i, is_max, subarray_max)
представляет наибольшую сумму, заканчивающуюся наi
-м элементе, гдеis_max
указывает, является ли элемент максимальным, аsubarray_max
— максимумом подмассива. Потом: