概要

連続した日程で働いたときの実質収入（日給の合計から交通費を引いた金額）の最大値を求める問題です。これは「最大部分配列問題」に帰着できます。

考察

問題の言い換え

\(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_i = A_i - 1\) と定義すれば、問題は「数列 \(B\) の連続部分列の和の最大値を求める」という問題に変換できます。

具体例で確認

例えば \(N = 3\)、\(A = [3, -1, 4]\) の場合： - \(B = [3-1, -1-1, 4-1] = [2, -2, 3]\) - 1日目だけ働く：\(2\) - 2日目だけ働く：\(-2\) - 3日目だけ働く：\(3\) - 1〜3日目働く：\(2 + (-2) + 3 = 3\)

最大値は \(3\) となります。

素朴なアプローチの問題点

すべての連続部分列を調べる素朴な方法は \(O(N^2)\) かかります。\(N \leq 2 \times 10^5\) の制約では TLE になる可能性があります。

アルゴリズム

Kadane’s Algorithm（カデインのアルゴリズム） を使用します。

このアルゴリズムは、連続部分列の最大和を \(O(N)\) で求める有名な手法です。

アイデア

配列を左から順に見ていき、各位置 \(i\) で「位置 \(i\) で終わる連続部分列の最大和」を管理します。

位置 \(i\) で終わる最大和は、次の2つのうち大きい方です： 1. 位置 \(i\) の要素だけを選ぶ：\(B_i\) 2. 位置 \(i-1\) で終わる最大和に \(B_i\) を加える：\(\text{current\_sum} + B_i\)

式で書くと： $\(\text{current\_sum} = \max(B_i, \text{current\_sum} + B_i)\)$

全体の最大値は、各位置での最大和の中で最も大きいものです。

動作例

\(B = [2, -2, 3]\) の場合：

\(i\)	\(B_i\)	current_sum	max_sum
0	2	2	2
1	-2	max(-2, 2-2)=0	2
2	3	max(3, 0+3)=3	3

最大値は \(3\) です。

計算量

• 時間計算量: \(O(N)\)

  • 配列 \(B\) の作成に \(O(N)\)
  • Kadane’s Algorithm で1回の走査に \(O(N)\)

• 空間計算量: \(O(N)\)

  • 配列 \(B\) の格納に \(O(N)\)
  • （\(B\) を作らず直接計算すれば \(O(1)\) も可能）

実装のポイント

1. 少なくとも1日は働くという制約があるため、max_sum の初期値を \(-\infty\) ではなく B[0] にしています。これにより、すべての \(B_i\) が負の場合でも正しく最大値が求まります。

2. 日給 \(A_i\) が最大 \(10^9\) の絶対値を持つため、答えが32ビット整数の範囲を超える可能性があります。Pythonでは自動で多倍長整数を扱えるため問題ありませんが、C++などでは long long を使う必要があります。

   ソースコード

def solve():
    N = int(input())
    A = list(map(int, input().split()))
    
    # 各日の実質収入は A_i - 1
    # 連続部分列の和の最大値を求める（Kadane's algorithm）
    # 少なくとも1日は働く必要がある
    
    # B_i = A_i - 1 として、Bの連続部分列の最大和を求める
    B = [a - 1 for a in A]
    
    # Kadane's algorithm (少なくとも1要素を含む)
    max_sum = B[0]
    current_sum = B[0]
    
    for i in range(1, N):
        current_sum = max(B[i], current_sum + B[i])
        max_sum = max(max_sum, current_sum)
    
    print(max_sum)

solve()

---

この解説は claude4.5opus によって生成されました。