Прибуток#2585

Прибуток (Розбір)

В задачі слід знайти таку підпослідовність підрядних чисел, яка матиме максимально можливу суму серед усіх можливих таких підпослідовностей. Якщо на підпослідовності $x_{i}, x_{i + 1}, ..., x_{j}$ x_i, x_{i+1}, ..., x_j досягається максимальна сума, то для будь-якого $k, 1 \leq k < i$ k, 1 \le k < i і $l, j < l \leq n$ l, j < l \le n сума елементів $x_{k}, ..., x_{i - 1}$ x_k, ..., x_{i-1} і $x_{j + 1}, ..., x_{l}$ x_{j+1}, ..., x_l буде від'ємною.

Алгоритм Кадане. Рухаємось по масиву зліва направо і накопичуємо у змінній $s$ поточну часткову суму. Якщо в якийсь момент $s$ буде від'ємною, то присвоюємо $s = 0$ s = 0. Максимум з усіх значень змінної $s$ за час проходу по масиву буде відповіддю на задачу.

Приклад

Для вхідної послідовності максимальний прибуток дорівнює $14$ .

Розглянемо приклад послідовності $X$ . Побудуємо часткові суми. Поточне значення часткової суми обнуляємо, коли сума стає меншою нуля і починаємо підрахунок суми з наступного числа. Максимальне значення серед усіх часткових сум дорівнює $6$ , що і є відповіддю. Шукана підпослідовність буде $4, - 2, 4$ 4, -2, 4.

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

Читаємо довжину послідовності $n$ . Обнуляємо значення максимального прибутку $ma x$ і поточної часткової суми $s$ .

scanf("%d",&n);
s = 0; max = 0;

Читаємо $n$ чисел. Кожне прочитане число $N u mb er$ додаємо до поточної суми $s$ і перераховуємо поточне значення прибутку $ma x$ . Якщо на якому-небудь кроці значення $s$ стало від'ємним, то встановлюємо його в нуль і продовжуємо процес.

for(i = 0; i < n; i++)
{
  scanf("%d",&Number);
  s += Number;
  if (s > max) max = s;
  if (s < 0) s = 0;
}

C++

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

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();
  }
}

Java

Python реалізація

Читаємо довжину послідовності $n$ . Обнуляємо значення максимального прибутку $ma x_p r o f i t$ max\_profit і поточної часткової суми $s$ .

n = int(input())
s = 0
max_profit = 0

Читаємо $n$ чисел. Кожне прочитане число $N u mb er$ додаємо до поточної суми $s$ і перераховуємо поточне значення прибутку $ma x_p r o f i t$ 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)