2585. Прибыль

Коровы открыли новый бизнес, и Фермер Джон хочет видеть, насколько они хорошо его ведут. Бизнес работает n (1 ≤ n ≤ 100000) дней, и в каждый i-ый день коровы записывают свою чистую прибыль P_i (-1000 ≤ P_i ≤ 1000).

Фермер Джон хочет найти самую большую прибыль, которую получили коровы в течение любого последовательного периода времени (обратите внимание, что последовательный период времени может иметь длину от одного дня до n дней). Помогите ему, написав программу для нахождения величины наибольшей непрерывной прибыли.

Вход. Первая строка содержит целое число n. Каждая из следующих n строк содержит одно целое число P_i.

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

Пример входа	Пример выхода
7 -3 4 9 -2 -5 8 -3	14

РЕШЕНИЕ

обработка последовательности

Анализ алгоритма

В задаче следует найти такую подпоследовательность подряд идущих чисел, которая будет иметь максимально возможную сумму среди всех возможных таких подпоследовательностей. Если на подпоследовательности x_i, x_i+1, ..., x_j достигается максимальная сумма, то для любого k, 1 £ k < i и l, j < l £ n сумма элементов x_k, ..., x_i-1 и x_j+1, ..., x_l будет отрицательной.

Алгоритм Кадана. Движемся по массиву слева направо и накапливаем в переменной s текущую частичную сумму. Если в какой-то момент s окажется отрицательной, то присвоим s = 0. Максимум из всех значений переменной s за время прохода по массиву и будет ответом на задачу.

Пример

Для входной последовательности максимальная прибыль равна 14.

Рассмотрим пример последовательности X. Построим частичные суммы. Текущее значение частичной суммы обнуляем когда сумма становится меньше нуля и начинаем отсчет суммы со следующего числа. Максимальное значение среди всех частичных сумм равно 6, что и является ответом. Искомой подпоследовательностью будет 4, -2, 4.

Реализация алгоритма

Читаем длину последовательности n. Обнуляем значение максимальной прибыли max и текущей частичной суммы s.

scanf("%d",&n);

s = 0; max = 0;

Читаем n чисел. Каждое прочитанное число Number добавляем к текущей сумме s и пересчитываем текущее значение прибыли max. Если на каком-то шаге значение s стало отрицательным, то положим его равным нулю и продолжим процесс.

for(i = 0; i < n; i++)

{

scanf("%d",&Number);

s += Number;

if (s > max) max = s;

if (s < 0) s = 0;

}

Выводим результат.

printf("%d\n",max);

Java реализация

import java.util.*;

public class Main

{

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

int n = con.nextInt();

int s = 0, max = 0;

for (int i = 0; i < n; i++)

{

int val = con.nextInt();

s += val;

if (s > max) max = s;

if (s < 0) s = 0;

}

System.out.println(max);

con.close();

}

}

Python реализация

Читаем длину последовательности n. Обнуляем значение максимальной прибыли max_profit и текущей частичной суммы s.

n = int(input())

s = 0

max_profit = 0

Читаем n чисел. Каждое прочитанное число Number добавляем к текущей сумме s и пересчитываем текущее значение прибыли max_profit. Если на каком-то шаге значение s стало отрицательным, то положим его равным нулю и продолжим процесс.

for i in range(n):

Number = int(input())

s += Number

if s > max_profit: max_profit = s

if s < 0: s = 0

Выводим результат.

print(max_profit)