公式

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

Claude 4.6 Opus (Thinking)

Overview

Given \(N\) days of profit/loss data in order, for each \(k = 1, 2, \ldots, N\), we need to find the “maximum subarray sum over the first \(k\) days.” This can be efficiently solved by incrementally applying Kadane’s algorithm.

Analysis

Naive Approach and Its Issues

For each \(k\), if we try all intervals \([l, r]\) (\(1 \leq l \leq r \leq k\)) and compute their sums, a single \(k\) takes \(O(k^2)\), and the total is \(O(N^3)\). Even using prefix sums, it takes \(O(N^2)\), which is too slow for \(N \leq 2 \times 10^5\) (TLE).

Key Insight

“Maximum subarray sum” is a well-known problem that can be solved in \(O(N)\) using Kadane’s algorithm. Moreover, in this problem we need to output answers for \(k = 1, 2, \ldots, N\) sequentially, and since Kadane’s algorithm inherently processes the array one element at a time from left to right, we can output the intermediate results directly as the answer for each \(k\).

Idea Behind Kadane’s Algorithm

We maintain two values:

  • \(\text{max\_ending\_here}\): the maximum sum of a contiguous subarray ending at the current position \(k\)
  • \(\text{max\_so\_far}\): the maximum sum of any contiguous subarray seen so far (the overall answer)

When processing the \(k\)-th element \(B_k\), the maximum subarray ending at \(k\) comes from one of two choices:

  1. Extend the previous subarray: \(\text{max\_ending\_here} + B_k\)
  2. Start fresh from \(B_k\): \(B_k\)

That is, we update \(\text{max\_ending\_here} = \max(\text{max\_ending\_here} + B_k,\ B_k)\).

Concrete example: For \(B = [3, -5, 4, 2, -1]\)

\(k\) \(B_k\) \(\text{max\_ending\_here}\) \(\text{max\_so\_far}\)
1 3 \(3\) \(3\)
2 -5 \(\max(3 + (-5),\ -5) = -2\) \(\max(3, -2) = 3\)
3 4 \(\max(-2 + 4,\ 4) = 4\) \(\max(3, 4) = 4\)
4 2 \(\max(4 + 2,\ 2) = 6\) \(\max(4, 6) = 6\)
5 -1 \(\max(6 + (-1),\ -1) = 5\) \(\max(6, 5) = 6\)

The output is \(3, 3, 4, 6, 6\).

Algorithm

  1. Initialize \(\text{max\_ending\_here} = B_1\), \(\text{max\_so\_far} = B_1\), and output the answer for \(k=1\).
  2. For \(k = 2, 3, \ldots, N\):
    • \(\text{max\_ending\_here} = \max(\text{max\_ending\_here} + B_k,\ B_k)\)
    • \(\text{max\_so\_far} = \max(\text{max\_so\_far},\ \text{max\_ending\_here})\)
    • Output \(\text{max\_so\_far}\) as the answer for the \(k\)-th line.

Complexity

  • Time complexity: \(O(N)\) — only a single pass through the array
  • Space complexity: \(O(N)\) — for storing the input array and output array (if only variables are used, \(O(1)\) suffices)

Implementation Notes

  • Empty subarrays cannot be chosen, so even if all values are negative, we must select the single largest element. In Kadane’s algorithm, \(\text{max\_ending\_here}\) always includes at least one element, so this condition is naturally satisfied.

  • Since the output consists of \(N\) lines, calling print each time can be slow. A key optimization is to accumulate results in a list and output them all at once using sys.stdout.write at the end.

  • Since \(B_i\) values can be \(\pm 10^9\) and \(N\) can be up to \(2 \times 10^5\), the total sum can reach approximately \(2 \times 10^{14}\). In Python there is no integer overflow, but in C++ and similar languages, long long is required.

    Source Code

import sys
input = sys.stdin.readline

def main():
    N = int(input())
    B = list(map(int, input().split()))
    
    # For each k, we need the maximum subarray sum of B[0..k-1]
    # This is the classic Kadane's algorithm, but we need to output for each prefix.
    # 
    # We maintain:
    # - max_ending_here: maximum sum of subarray ending at current position (must include current element)
    # - max_so_far: overall maximum subarray sum seen so far
    
    out = []
    max_ending_here = B[0]
    max_so_far = B[0]
    out.append(max_so_far)
    
    for k in range(1, N):
        # Kadane's: extend previous subarray or start new one at k
        if max_ending_here + B[k] > B[k]:
            max_ending_here = max_ending_here + B[k]
        else:
            max_ending_here = B[k]
        
        if max_ending_here > max_so_far:
            max_so_far = max_ending_here
        
        out.append(max_so_far)
    
    sys.stdout.write('\n'.join(map(str, out)) + '\n')

main()

This editorial was generated by claude4.6opus-thinking.