Overview

A problem where you work part-time on consecutive days and maximize the net income (total daily wages minus transportation costs).

Analysis

Each day has a daily wage \(A_i\), and working on any day costs \(1\) yen in transportation fees. Therefore, the net income when working over a consecutive interval \([i, j]\) is: $\( (A_i + A_{i+1} + \cdots + A_j) - (j - i + 1) \)$

If we define \(B_i = A_i - 1\) by subtracting \(1\) yen from each daily wage, this becomes: $\( B_i + B_{i+1} + \cdots + B_j \)\( In other words, the problem reduces to finding the maximum sum of a contiguous subarray of array \)B$.

A naive approach that tries all intervals \([i, j]\) takes \(O(N^2)\), which would TLE since \(N\) can be up to \(2 \times 10^5\). Instead, we can solve this in linear time using Kadane’s Algorithm, a well-known algorithm for finding the maximum contiguous subarray sum.

Algorithm

1. Create a new array \(B\) by subtracting the transportation cost of \(1\) yen from each daily wage: $\( B_i = A_i - 1 \)$

2. While precomputing prefix sums of array \(B\) would allow fast computation of any interval sum, this solution directly uses Kadane’s Algorithm, so prefix sums are not strictly necessary.

3. Kadane’s Algorithm:

   • Traverse array \(B\) from left to right while maintaining the “current interval sum.”
   • If the interval sum becomes negative, it is better to start a new interval from the next position to maximize future sums, so reset the interval sum.
   • Record the maximum value encountered along the way.

Example

For example, given the input:

5
3 -1 2 -2 3

• \(B = [2, -2, 1, -3, 2]\)
• Kadane’s Algorithm process:
  • Initial: current_sum = 0, max_profit = -∞
  • i=0: current_sum = 2 → update → max_profit = 2
  • i=1: current_sum = 0 (2 + (-2) = 0)
  • i=2: current_sum = 1 → no update
  • i=3: current_sum = -2 → reset (back to 0)
  • i=4: current_sum = 2 → no update
• Result: maximum net income is \(2\)

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(N)\) (used for storing array \(B\) and prefix sums)

※ In practice, if you apply Kadane’s Algorithm directly without using prefix sums, the space complexity can be reduced to \(O(1)\).

Implementation Notes

• By first creating array \(B\) where \(1\) yen is subtracted from each daily wage, the problem reduces to “maximum contiguous subarray sum.”

• In Kadane’s Algorithm, don’t forget to reset the interval sum when it becomes negative.

• Since you must work at least one day, the answer is always the sum of a subarray containing at least one element.

  Source Code

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

---

This editorial was generated by qwen3-coder-480b.