Overview

This problem can be thought of as treating the “net income” — each day’s wage minus 1 yen for transportation — as a single array, and finding the maximum sum of a non-empty contiguous subarray.

Analysis

Rephrasing the Problem

If we denote the wage on day \(i\) as \(A_i\), then the net income for that day is \(B_i = A_i - 1\) yen. The total income when Takahashi works consecutively from day \(i\) to day \(j\) can be expressed as: $\((A_i + A_{i+1} + \cdots + A_j) - (j - i + 1) = (A_i - 1) + (A_{i+1} - 1) + \cdots + (A_j - 1)\)\( In other words, the problem reduces to maximizing the sum of a contiguous subsequence of the array \)B = [A_1-1, A_2-1, \dots, A_N-1]$.

Why a Naive Approach Won’t Work

If we try to examine all possible contiguous intervals \((i, j)\), there are approximately \(\frac{N^2}{2}\) combinations. Given the constraint \(N \le 2 \times 10^5\), we get \(N^2 \approx 4 \times 10^{10}\), which cannot be computed within the time limit. Therefore, a more efficient algorithm of \(O(N)\) or \(O(N \log N)\) is needed.

Efficient Solution

This problem is a well-known problem called the “Maximum Subarray Problem,” and it can be solved by scanning the array just once using Kadane’s Algorithm.

Algorithm

Kadane’s Algorithm

Based on the concept of dynamic programming (DP), we sequentially update the following values:

1. current_max: The maximum sum among all contiguous subarrays ending at day \(i\)
2. max_net_income: The maximum sum among all subarrays found so far

At each step \(i\), current_max is updated as follows: - Choose the larger of “adding today’s net income to the maximum sum up to the previous day” or “starting fresh from today.” - Formula: \(dp[i] = \max(B_i, dp[i-1] + B_i)\)

However, since this problem requires “working at least one day,” the initial value is set to the net income of the first day \(A_1 - 1\), and the above update is performed from the second day onward.

Complexity

• Time Complexity: \(O(N)\)
  • Since we only scan the array once, the processing completes in linear time with respect to the number of elements \(N\).
• Space Complexity: \(O(N)\)
  • \(O(N)\) memory is used to store the input values. The computation itself only requires a few variables, so it can be done in \(O(1)\).

Implementation Notes

• Fast Input: When \(N\) is large in Python, reading all input at once with sys.stdin.read().split() is faster than repeatedly calling input().

• Initialization: Since all daily wages may be very low (resulting in negative net income), the variable holding the maximum must not be initialized to 0. It must be initialized with an appropriate value that considers cases such as “working only one day” (e.g., the net income of the first day).

• Maintaining Continuity: When current_max becomes negative, discarding the accumulated sum and starting a fresh count from the next day (current_max = net_income) correctly maintains the maximum value among contiguous intervals.

  Source Code

import sys

def solve():
    # 標準入力からすべてのデータを読み込み、空白（スペース、改行など）で分割してトークンのリストを作成します。
    # Nが最大2*10^5程度であれば、この方法がPythonにおいて高速に動作します。
    data = sys.stdin.read().split()
    if not data:
        return
    
    # イテレータを使用してデータを1つずつ処理します。
    it = iter(data)
    try:
        # 1つ目の要素は日数Nです。
        n = int(next(it))
    except StopIteration:
        return
    
    # この問題は「実質的な収入（日給 - 1円）」の「空でない連続部分配列の最大和」を求める問題です。
    # 少なくとも1日は働く必要があるため、カデインのアルゴリズム（Kadane's Algorithm）を
    # 1日以上の連続期間を考慮する形で適用します。
    
    try:
        # 最初の日の実質収入 (A_1 - 1) で初期化します。
        # 制約により N >= 1 なので、必ず1日目のデータは存在します。
        first_wage = int(next(it))
        current_max = first_wage - 1
        max_net_income = current_max
    except StopIteration:
        return
    
    # 2日目からN日目までのデータを順番に処理します。
    for wage_str in it:
        # その日の実質的な収入
        net_income = int(wage_str) - 1
        
        # カデインのアルゴリズムの更新ルール：
        # 直前までの累積和（current_max）が正であれば、それを引き継ぐ方が
        # 現在の単独の日から新しく始めるよりも得になります。
        if current_max > 0:
            current_max += net_income
        else:
            # 直前までの和が0以下なら、今日から新しく働き始める方が（または今日のみ働く方が）得、
            # あるいは今日から始めるしかありません（連続性が途切れるため）。
            current_max = net_income
        
        # これまでに見つかった最大の実質収入を更新します。
        if current_max > max_net_income:
            max_net_income = current_max
    
    # 求まった最大の実質収入を出力します。
    print(max_net_income)

if __name__ == '__main__':
    solve()

---

This editorial was generated by gemini-3-flash-preview.