概要

この問題は、各日の日給から交通費1円を引いた「実質収入」を一つの配列とみなし、その空でない連続する部分配列の和の最大値を求める問題です。

考察

問題の言い換え

\(i\) 日目の日給を \(A_i\) とすると、その日の実質的な収入は \(B_i = A_i - 1\) 円です。 高橋君が \(i\) 日目から \(j\) 日目まで連続して働いたときの総収入は、以下のように表せます。 $\((A_i + A_{i+1} + \cdots + A_j) - (j - i + 1) = (A_i - 1) + (A_{i+1} - 1) + \cdots + (A_j - 1)\)\( つまり、配列 \)B = [A_1-1, A_2-1, \dots, A_N-1]$ の連続する部分列の和を最大化する問題に帰着されます。

なぜ素朴な方法では解けないか

すべての連続する区間 \((i, j)\) の組み合わせを調べようとすると、区間の選び方は約 \(\frac{N^2}{2}\) 通り存在します。 今回の制約は \(N \le 2 \times 10^5\) であるため、\(N^2 \approx 4 \times 10^{10}\) となり、実行制限時間内に計算が終わりません。そのため、より効率的な \(O(N)\) や \(O(N \log N)\) のアルゴリズムが必要です。

効率的な解法

この問題は「最大部分配列和問題」と呼ばれる有名な問題であり、カデインのアルゴリズム (Kadane’s Algorithm) を用いることで、配列を一度走査するだけで解くことができます。

アルゴリズム

カデインのアルゴリズム

動的計画法（DP）の考え方に基づき、以下の値を順に更新していきます。

1. current_max: \(i\) 日目で終わる連続部分配列の中での最大和
2. max_net_income: これまでに見つかったすべての部分配列の中での最大和

各ステップ \(i\) において、current_max は次のように更新されます。 - 「前の日までの最大和に今日の実質収入を加える」か「今日から新しく働き始める」かの大きい方を選ぶ。 - 数式：\(dp[i] = \max(B_i, dp[i-1] + B_i)\)

ただし、今回の問題は「少なくとも1日は働く必要がある」ため、初期値は第1日目の実質収入 \(A_1 - 1\) とし、2日目以降から上記の更新を行います。

計算量

• 時間計算量: \(O(N)\)
  • 配列を1回スキャンするだけなので、要素数 \(N\) に対して線形時間で処理が完了します。
• 空間計算量: \(O(N)\)
  • 入力値を保持するために \(O(N)\) のメモリを使用します。計算自体は変数を数個用意するだけなので \(O(1)\) で可能です。

実装のポイント

• 入力の高速化: Pythonで \(N\) が大きい場合、input() を繰り返すよりも sys.stdin.read().split() で一括で読み込む方が高速です。

• 初期値の設定: すべての日給が非常に低い（実質収入がマイナスになる）場合があるため、最大値を保持する変数を 0 で初期化してはいけません。必ず「1日だけ働いた場合」などを考慮した適切な値（例：最初の日の実質収入）で初期化する必要があります。

• 連続性の維持: current_max が負になった場合、それまでの蓄積を捨てて次の日から新しくカウントし直す（current_max = net_income）ことで、連続する区間の中での最大値を正しく維持できます。

  ソースコード

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()

---

この解説は gemini-3-flash-preview によって生成されました。