Overview

For each \(k\), we need to find the maximum sum of a contiguous subarray within the first \(k\) days. We solve this efficiently using Kadane’s algorithm.

Analysis

A naive approach that computes the sum of all contiguous subarrays for each \(k\) would take \(O(N^3)\) time, which is far too slow given the constraint \(N \leq 2 \times 10^5\).

The key observation is that the maximum subarray sum up to day \(k\) is one of the following two values: 1. A subarray containing only day \(k\) (value: \(B_k\)) 2. A subarray formed by extending the maximum subarray ending at day \(k-1\) (value: \(dp[k-1] + B_k\))

Here, \(dp[i]\) represents the maximum sum of a contiguous subarray ending at day \(i\). Furthermore, the overall maximum can be updated at each step by comparing \(dp[i]\) with the previous maximum \(ans[i-1]\).

Algorithm

We apply Kadane’s algorithm: 1. Initialize \(dp[0] = B[0]\) (only the first day) 2. Initialize \(ans[0] = B[0]\) 3. For \(i = 1\) to \(N-1\), repeat the following: - \(dp[i] = \max(B[i], dp[i-1] + B[i])\) (current day only vs. extending the previous subarray) - \(ans[i] = \max(ans[i-1], dp[i])\) (previous maximum vs. new subarray sum) 4. Output the \(ans\) array in order

This method efficiently computes the maximum subarray sum for each \(k\).

Complexity

• Time complexity: \(O(N)\)
  • Only a single pass through the array
• Space complexity: \(O(N)\)
  • Uses the \(dp\) array and the \(ans\) array

Implementation Notes

• Properly set the first element during initialization

• To handle negative values, ensure each subarray contains at least one day

• Be careful with array indexing (0-indexed)

• Use an appropriate integer type to handle large numbers

  Source Code

import sys

def main():
    data = sys.stdin.read().split()
    n = int(data[0])
    B = list(map(int, data[1:1+n]))
    
    dp = [0] * n
    ans = [0] * n
    
    dp[0] = B[0]
    ans[0] = B[0]
    
    for i in range(1, n):
        dp[i] = max(B[i], dp[i-1] + B[i])
        ans[i] = max(ans[i-1], dp[i])
    
    for a in ans:
        print(a)

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.