Profit#2585

Profit (Editorial)

In this problem you should find a subsequence of consecutive numbers that will have the maximum possible sum among all such subsequences. If the maximum sum is achieved on the subsequence $x_{i}, x_{i + 1}, ..., x_{j}$ x_i, x_{i+1}, ..., x_j, then for any $k, 1 \leq k < i$ k, 1 \le k < i и $l, j < l \leq n$ l, j < l \le n, the sum of elements $x_{k}, ..., x_{i - 1}$ x_k, ..., x_{i-1} and $x_{j + 1}, ..., x_{l}$ x_{j+1}, ..., x_l will be negative.

Kadane's algorithm. Move through the array from left to right and accumulate the current partial sum in the variable $s$ . If at any moment $s$ becomes negative, set $s = 0$ s = 0. The maximum of all values of the variable $s$ during the traversal of the array will be the answer to the problem.

Example

For the input sequence the maximum profit is $14$ .

Consider an example of sequence $X$ . Construct the partial sums. Reset the current value of the partial sum to zero when the sum becomes less than zero, and start counting the sum from the next number. The maximum value among all partial sums is $6$ , which is the answer. The desired subsequence will be $4, - 2, 4$ 4, -2, 4.

Algorithm implementation

Read the length of the sequence $n$ . Initialize the value of the maximum profit $ma x$ and the current partial sum $s$ to zero.

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

Read $n$ integers. Each read integer $N u mb er$ is added to the current sum $s$ and we recompute the current value of profit $ma x$ . If at any step the value of $s$ becomes negative, set it to zero and continue the process.

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

C++

Print the answer.

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

Java implementation

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 implementation

Read the length of the sequence $n$ . Initialize the value of the maximum profit $ma x_p r o f i t$ max\_profit and the current partial sum $s$ to zero.

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

Read $n$ integers. Each read integer $N u mb er$ is added to the current sum $s$ and we recompute the current value of profit $ma x_p r o f i t$ max\_profit. If at any step the value of $s$ becomes negative, set it to zero and continue the process.

for i in range(n):
  Number = int(input())
  s += Number
  if s > max_profit: max_profit = s
  if s < 0: s = 0

Print the answer.

print(max_profit)