Overview

For each \(k=1..N\), find the maximum subarray sum (maximum sum over all contiguous subarrays of length \(\ge 1\)) considering days \(1\) through \(k\).

Analysis

What we want is the maximum subarray sum of the array \(B_1..B_k\). If we compute this independently for each \(k\):

• Trying all intervals \((l,r)\) takes \(O(k^2)\)
  
• Repeating this for \(k=1..N\) gives a total of \(O(N^3)\) (or \(O(N^2)\) with some optimization)

This is too slow for \(N \le 2\times 10^5\) (TLE).

The key observations are the following two points:

1. The “answer up to \(k\)” can be updated from the “answer up to \(k-1\)”
   
2. If we know the maximum subarray sum ending at \(k\) (with the right endpoint fixed), we can update the overall maximum

Specifically, letting \(x=B_k\) be the value on day \(k\), the maximum subarray sum ending at day \(k\) is the larger of: - The subarray consisting of only day \(k\): sum is \(x\) - Extending the “maximum subarray sum ending at day \(k-1\)” by adding \(x\): sum is \(\text{cur}+x\)

If the accumulated subarray sum so far is negative, it is better to start a new subarray rather than extending.

Also, the maximum subarray sum within \(1..k\) (the answer) is the maximum of: - The maximum value already achieved in \(1..k-1\) - The maximum subarray sum ending at \(k\)

For example, when \(B=[-2, 3, -1, 4]\): - \(k=1\): maximum is \(-2\) - \(k=2\): \(3\) alone is best, so maximum is \(3\) - \(k=3\): \(3+(-1)=2\) is better than \(-1\), maximum remains \(3\) - \(k=4\): \(2+4=6\) is best, maximum is \(6\)

By performing this update one step at a time, we can efficiently compute the answer for all \(k\).

Algorithm

We adapt Kadane’s algorithm (maximum subarray sum) to output the answer for each prefix \(1..k\).

• \(\text{cur}\): maximum subarray sum ending at the current position \(i\)
  $\( \text{cur} = \max(B_i,\ \text{cur}+B_i) \)$
• \(\text{best}\): maximum subarray sum so far (over \(1..i\))
  $\( \text{best} = \max(\text{best},\ \text{cur}) \)$

By outputting \(\text{best}\) for each \(i=1..N\), we get the answer for \(k=i\).

Key point: Since the empty subarray is not allowed, we initialize not with \(0\) but with \(B_1\) (to correctly return the maximum negative value even when all values are negative).

Complexity

• Time complexity: \(O(N)\) (each element is processed exactly once)
• Space complexity: \(O(1)\) (constant excluding output; \(O(N)\) if output is stored in the implementation)

Implementation Notes

• Initialize with cur = best = B[0] (to handle the prohibition of empty subarrays)

• The update formula is cur = max(x, cur + x) (either “extend” or “start new”)

• The answer for each \(k\) is simply the current value of best

• Since the input can be large, use sys.stdin.buffer.read() for faster I/O

  Source Code

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return
    n = data[0]
    b = data[1:1+n]

    res = []
    cur = b[0]
    best = b[0]
    res.append(str(best))

    for i in range(1, n):
        x = b[i]
        cur = max(x, cur + x)
        if cur > best:
            best = cur
        res.append(str(best))

    sys.stdout.write("\n".join(res))

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.