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.
- 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\)
- Record
global_maxas the answer for \(k=1\). - For \(i = 2, 3, \ldots, N\), perform the following updates:
- If
current_maxis positive, add \(B_i\) tocurrent_max. - If
current_maxis 0 or less, overwritecurrent_maxwith \(B_i\) (restart). - If
current_maxexceedsglobal_max, updateglobal_max. - Record the current
global_maxas the answer for \(k=i\).
- If
- 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_maxorglobal_maxto \(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 callingprinteach 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.