Overview

Given daily profit/loss data, the problem asks us to sequentially find the maximum contiguous subarray sum at each point in time.

Analysis

This problem is essentially the “Maximum Subarray Problem” adapted to an online query setting. A brute-force approach would try all intervals \([l, r]\) for each \(k\) to find the answer, but this results in \(O(N^3)\) complexity, which is impractical since \(N\) can be up to \(2 \times 10^5\).

The key insight is that instead of independently computing the maximum subarray sum for each \(k\), we can efficiently update using previous results. In other words, we can leverage information about the optimal interval obtained up to a given day to update the optimal solution for the next day.

Based on this idea, a dynamic programming approach becomes effective. A particularly well-known technique is Kadane’s Algorithm, which can find the maximum subarray sum in linear time.

Algorithm

In this problem, for each \(k = 1, 2, ..., N\), we need to find the maximum sum of a contiguous subarray considering only the first \(k\) elements of the array.

To do this, we maintain the following variables:

• max_ending_here: the maximum sum of a contiguous subarray that must include the current position
• max_so_far: the overall maximum value across the entire range seen so far

The algorithm proceeds as follows:

1. For the first element \(B_0\), the only possible interval is just that element, so we set it as the initial value:
   • max_ending_here = B[0]
   • max_so_far = B[0]
2. For each \(i = 1, 2, ..., N-1\), do the following:
   • When adding the new element \(B[i]\), choose whether to continue the existing interval or start a new one:
     • max_ending_here = max(B[i], max_ending_here + B[i])
   • Update the overall maximum:
     • max_so_far = max(max_so_far, max_ending_here)
3. Output the max_so_far computed at each step, and we are done.

By doing this, we can update the maximum subarray sum in \(O(1)\) at each step, solving the entire problem in \(O(N)\).

Concrete Example

For example, if the input is [1, -3, 2, 1, -1]:

k	B[k]	max_ending_here	max_so_far
1	1	1	1
2	-3	-2	1
3	2	2	2
4	1	3	3
5	-1	2	3

Therefore, the output is:

1
1
2
3
3

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(1)\) (excluding input)

Implementation Notes

• The key point is reusing the “optimal solution up to that point” for each day

• max_ending_here is the maximum sum of an interval that must include the current position, and it is updated at every step

• max_so_far is the maximum value seen across the entire process and must always be maintained

• Handling the first day as a special case at the beginning allows the rest to be treated uniformly within the loop, which is convenient

  Source Code

import sys
input = sys.stdin.read

def main():
    data = input().split()
    N = int(data[0])
    B = list(map(int, data[1:]))

    max_ending_here = B[0]
    max_so_far = B[0]
    print(max_so_far)

    for i in range(1, N):
        max_ending_here = max(B[i], max_ending_here + B[i])
        max_so_far = max(max_so_far, max_ending_here)
        print(max_so_far)

if __name__ == "__main__":
    main()

---

This editorial was generated by qwen3-coder-480b.