概要

連続した日程でアルバイトを行い、実質収入（日給の合計から交通費を引いたもの）を最大化する問題。

考察

各日には日給 \(A_i\) が設定されており、働く日には交通費として \(1\) 円がかかる。したがって、連続する区間 \([i, j]\) で働くときの実質収入は、
$\( (A_i + A_{i+1} + \cdots + A_j) - (j - i + 1) \)$
となる。

これは、各日給から \(1\) 円を引いた値 \(B_i = A_i - 1\) を考えると、
$\( B_i + B_{i+1} + \cdots + B_j \)\( と等しくなる。つまり、配列 \)B$ の連続部分列の和の最大値を求めればよいことがわかる。

素朴な方法では、すべての区間 \([i, j]\) を試すと \(O(N^2)\) かかり、\(N\) が最大 \(2 \times 10^5\) なのでTLEになる。
そこで、「連続部分列の和の最大値」を求める有名アルゴリズムである Kadane’s Algorithm を用いることで、線形時間で解ける。

アルゴリズム

1. 各要素について、日給から交通費 \(1\) 円を引いた新しい配列 \(B\) を作る：
   $\( B_i = A_i - 1 \)$

2. 配列 \(B\) の累積和を前処理で計算しておくと、任意の区間和が高速に求められるようになるが、今回の解法では直接 Kadane のアルゴリズムを使うので、累積和は必須ではない。

3. Kadane’s Algorithm：

   • 配列 \(B\) に対して、左から順に見ていきながら「現在の区間和」を管理する。
   • 区間和が負になったら、それ以降の和を大きくするためには新たに区間を始める方が良いので、区間和をリセットする。
   • 途中で得られた最大値を記録していく。

例

例えば、入力が

5
3 -1 2 -2 3

のとき、
- \(B = [2, -2, 1, -3, 2]\)
- Kadane’s Algorithm の過程： - 初期：current_sum = 0, max_profit = -∞ - i=0: current_sum = 2 → 更新 → max_profit = 2 - i=1: current_sum = 0 （2 + (-2) = 0） - i=2: current_sum = 1 → 更新せず - i=3: current_sum = -2 → リセット（0に戻す） - i=4: current_sum = 2 → 更新せず - 結果：最大実質収入は \(2\)

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(N)\) （配列 \(B\) および累積和の保存に使用）

※ 実際には累積和は使わず、直接 Kadane を適用すれば空間計算量も \(O(1)\) にできる。

実装のポイント

• 各日給から \(1\) 円を引いた配列 \(B\) を先に作ることで、問題を「最大部分連続和」に帰着できる。

• Kadane のアルゴリズムでは、区間和が負になった時点でリセットすることを忘れない。

• 少なくとも1日は働かなければならないので、答えは必ず1つ以上の要素を持つ部分列の和になる。

  ソースコード

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    N = int(data[0])
    A = list(map(int, data[1:]))

    # 各日給から1円を引いておく（交通費）
    B = [a - 1 for a in A]

    # 累積和を計算
    S = [0] * (N + 1)
    for i in range(N):
        S[i + 1] = S[i] + B[i]

    # 最大部分配列和（Kadane's algorithm）
    max_profit = float('-inf')
    current_sum = 0
    for i in range(1, N + 1):
        current_sum += B[i - 1]
        if current_sum > max_profit:
            max_profit = current_sum
        if current_sum < 0:
            current_sum = 0

    print(max_profit)

if __name__ == "__main__":
    main()

---

この解説は qwen3-coder-480b によって生成されました。