Сумма чисел в массиве

@Rorik · Регистрация: 28.06.2020

Студворк — интернет-сервис помощи студентам

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

Примечание. Фактически требуется найти такие i и j (i≤j), что сумма всех элементов массива от ai до aj включительно будет максимальна.

Входные данные

На вход программе сначала подается натуральное n≤100000 — количество элементов в массиве. Далее, по одному в строке расположены сами элементы массива — целые числа, по модулю не превосходящие 30000.

Выходные данные

Выдайте пару искомых значений индексов. Если таких пар несколько, то j должно быть минимально возможным, а при равных j значение i должно быть максимально возможным.

Примеры
Ввод
Вывод
5
-1
2
3
-2
2
2
3
7
2
-2
3
-1
5
-2
7
3
7

@GulgDev · 05.07.2020, 10:33

Python
1
print(sum([int(input()) for i in range(int(input())]))

@iSmokeJC · 05.07.2020, 12:52

Hyppoprogramm,

@Semen-Semenich · 05.07.2020, 13:24

Hyppoprogramm, иногда полезно прочитать внимательно и вникнуть в задание

Сообщение от Rorik

найдите непрерывный кусок

@err · 07.07.2020, 15:54

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
n=int(input())
p=[0]*(n+1)
for i in range(n):
    s=int(input())
    p[i+1]=p[i]+s
ibest=0
jbest=1
imin=0
for j in range(2,n+1):
    if p[j-1]<p[imin]:
        imin=j-1
    elif p[j-1]==p[imin] and j-1>imin:
        imin=j-1
    if p[j]-p[imin]>p[jbest]-p[ibest]:
        jbest=j
        ibest=imin
    elif p[j]-p[imin]==p[jbest]-p[ibest]:
        if j<jbest:
            jbest=j
            ibest=imin
        elif j==jbest:
            if imin>ibest:
                jbest=j
                ibest=imin
print(ibest+1,jbest)

@Infeeqs · 07.07.2020, 16:03

как тут отличить где ввод а где вывод

Добавлено через 1 минуту
рорик

@eaa · 08.07.2020, 09:00

За один проход алгоритм видимо должен быть O(1) по памяти, а не O(n) как с префикс-суммами.

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL3_image 8Observer8 10.02.2026 Содержание блога Библиотека SDL3_image содержит инструменты для расширенной работы с изображениями. Пошагово создадим проект для загрузки изображения формата PNG с альфа-каналом (с прозрачным. . .	Установка Qt-версии Lazarus IDE в Debian Trixie Xfce volvo 10.02.2026 В общем, достали меня глюки IDE Лазаруса, собранной с использованием набора виджетов Gtk2 (конкретно: если набирать текст в редакторе и вызвать подсказку через Ctrl+Space, то после закрытия окошка. . .
SDL3 для Web (WebAssembly): Работа со звуком через SDL3_mixer 8Observer8 08.02.2026 Содержание блога Пошагово создадим проект для загрузки звукового файла и воспроизведения звука с помощью библиотеки SDL3_mixer. Звук будет воспроизводиться по клику мышки по холсту на Desktop и по. . .	SDL3 для Web (WebAssembly): Основы отладки веб-приложений на SDL3 по USB и Wi-Fi, запущенных в браузере мобильных устройств 8Observer8 07.02.2026 Содержание блога Браузер Chrome имеет средства для отладки мобильных веб-приложений по USB. В этой пошаговой инструкции ограничимся работой с консолью. Вывод в консоль - это часть процесса. . .	SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве 8Observer8 02.02.2026 Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .	Философия технологии iceja 01.02.2026 На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .

@Rorik 25 / 14 / 2 Регистрация: 28.06.2020 Сообщений: 50

	Сумма чисел в массиве 05.07.2020, 02:12. Показов 11428. Ответов 6 Метки нет (Все метки) В одномерном массиве, заполненном произвольными целыми числами, за один проход найдите непрерывный кусок, сумма чисел в котором максимальна. Примечание. Фактически требуется найти такие i и j (i≤j), что сумма всех элементов массива от ai до aj включительно будет максимальна. Входные данные На вход программе сначала подается натуральное n≤100000 — количество элементов в массиве. Далее, по одному в строке расположены сами элементы массива — целые числа, по модулю не превосходящие 30000. Выходные данные Выдайте пару искомых значений индексов. Если таких пар несколько, то j должно быть минимально возможным, а при равных j значение i должно быть максимально возможным. Примеры Ввод Вывод 5 -1 2 3 -2 2 2 3 7 2 -2 3 -1 5 -2 7 3 7 0

@iSmokeJC 19530 / 11067 / 2931 Регистрация: 21.10.2017 Сообщений: 23,294
	05.07.2020, 12:52
	Hyppoprogramm, 0

@Infeeqs 8 / 8 / 0 Регистрация: 15.02.2020 Сообщений: 195
	07.07.2020, 16:03
	как тут отличить где ввод а где вывод Добавлено через 1 минуту рорик 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	08.07.2020, 09:00
	За один проход алгоритм видимо должен быть O(1) по памяти, а не O(n) как с префикс-суммами. 0