Official

B - 損益の最大区間和 / Maximum Subarray Sum of Profit and Loss Editorial by admin

Gemini 3.1 Pro (Thinking)

Overview

Given a sequence, for each \(k = 1, 2, \ldots, N\), find the maximum sum of a contiguous subsequence (maximum subarray sum) considering only the first \(k\) elements of the sequence.

Analysis

This problem can be described as outputting all intermediate states of the well-known “Maximum Subarray Sum” problem.

First, let’s consider a naive approach. For each \(k\), if we try to compute the sum of every interval \((l, r)\) and find the maximum, it takes \(O(k^2)\) time even with prefix sums. Repeating this for \(k = 1\) through \(N\) results in an overall time complexity of \(O(N^3)\). With the constraint \(N = 2 \times 10^5\), this far exceeds the time limit (TLE).

To optimize the computation, the key insight is to focus on “the maximum sum of an interval ending on day \(i\)”. When trying to maximize the sum of an interval ending on day \(i\), there are only two choices: 1. Extend the interval ending on day \(i-1\) by appending day \(i\)’s profit/loss \(B_i\). 2. Discard the previous interval and start a new interval consisting of only day \(i\).

Which choice to make depends on whether the maximum sum of the interval ending on day \(i-1\) is “positive” or “0 or less”: - If the previous sum is positive (\(>0\)), adding \(B_i\) to it yields a larger sum. - If the previous sum is in deficit (\(\le 0\)), inheriting the previous interval would be a loss, so restarting with \(B_i\) alone yields a larger sum.

By maintaining the running maximum of “the maximum sum of an interval ending at each day” computed this way, we obtain the answer for each \(k\).

Algorithm

This solution is an application of Kadane’s Algorithm.

  1. Prepare two variables, both initialized to the first element \(B_1\).
    • current_max: the maximum sum of an interval that necessarily ends at the most recent day \(i\)
    • global_max: the maximum sum over all intervals from day \(1\) through day \(i\)
  2. Record global_max as the answer for \(k=1\).
  3. For \(i = 2, 3, \ldots, N\), perform the following updates:
    • If current_max is positive, add \(B_i\) to current_max.
    • If current_max is 0 or less, overwrite current_max with \(B_i\) (restart).
    • If current_max exceeds global_max, update global_max.
    • Record the current global_max as the answer for \(k=i\).
  4. Output the recorded answers in order.

Concrete example: \(B = [3, -5, 4, -1, 3]\) - \(i=1\) (\(B_1=3\)): current_max = \(3\), global_max = \(3\) (output: \(3\)) - \(i=2\) (\(B_2=-5\)): Previous current_max (\(3\)) \(> 0\), so add. current_max = \(3 + (-5) = -2\). global_max remains \(3\) (output: \(3\)) - \(i=3\) (\(B_3=4\)): Previous current_max (\(-2\)) \(\le 0\), so restart. current_max = \(4\). global_max is updated to \(4\) (output: \(4\)) - \(i=4\) (\(B_4=-1\)): Previous current_max (\(4\)) \(> 0\), so add. current_max = \(4 + (-1) = 3\). global_max remains \(4\) (output: \(4\)) - \(i=5\) (\(B_5=3\)): Previous current_max (\(3\)) \(> 0\), so add. current_max = \(3 + 3 = 6\). global_max is updated to \(6\) (output: \(6\))

Complexity

  • Time complexity: \(O(N)\)
    • We only loop through the array once from the beginning, performing additions and comparisons, so the processing completes in time proportional to the number of elements \(N\).
  • Space complexity: \(O(N)\)
    • \(O(N)\) memory is used to store the input data and the output array. The algorithm itself requires only a constant number of additional variables, so space efficiency is also excellent.

Implementation Notes

  • The condition that an empty interval cannot be chosen: Even if all days are in deficit (negative numbers), at least one day must be selected. Therefore, do not initialize current_max or global_max to \(0\); always initialize them with the value of day \(1\), \(B_1\).

  • Fast I/O: Since \(N\) can be as large as \(2 \times 10^5\), in Python it is faster to accumulate answers as strings in a list (array) and output them all at once with '\n'.join(out) at the end, rather than calling print each time.

    Source Code

import sys

def main():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    B = [int(x) for x in input_data[1:N+1]]
    
    current_max = B[0]
    global_max = B[0]
    
    out = [str(global_max)]
    
    for i in range(1, N):
        val = B[i]
        if current_max > 0:
            current_max += val
        else:
            current_max = val
            
        if current_max > global_max:
            global_max = current_max
            
        out.append(str(global_max))
        
    print('\n'.join(out))

if __name__ == '__main__':
    main()

This editorial was generated by gemini-3.1-pro-thinking.