Overview

This problem asks us to find the maximum net income (total daily wages minus transportation costs) when working on consecutive days. This can be reduced to the “Maximum Subarray Problem.”

Analysis

Reformulating the Problem

The net income when working from day \(i\) to day \(j\) is:

\[(A_i + A_{i+1} + \cdots + A_j) - (j - i + 1)\]

This can be rewritten as:

\[(A_i - 1) + (A_{i+1} - 1) + \cdots + (A_j - 1)\]

In other words, if we define \(B_i = A_i - 1\), the problem transforms into “finding the maximum sum of a contiguous subarray of sequence \(B\).”

Verification with a Concrete Example

For example, when \(N = 3\) and \(A = [3, -1, 4]\): - \(B = [3-1, -1-1, 4-1] = [2, -2, 3]\) - Working only day 1: \(2\) - Working only day 2: \(-2\) - Working only day 3: \(3\) - Working days 1-3: \(2 + (-2) + 3 = 3\)

The maximum value is \(3\).

Issues with the Naive Approach

A naive method that examines all contiguous subarrays takes \(O(N^2)\) time. With the constraint \(N \leq 2 \times 10^5\), this may result in TLE.

Algorithm

We use Kadane’s Algorithm.

This algorithm is a well-known technique for finding the maximum subarray sum in \(O(N)\) time.

Idea

We iterate through the array from left to right, maintaining at each position \(i\) the “maximum sum of a contiguous subarray ending at position \(i\).”

The maximum sum ending at position \(i\) is the larger of these two options: 1. Select only the element at position \(i\): \(B_i\) 2. Add \(B_i\) to the maximum sum ending at position \(i-1\): \(\text{current\_sum} + B_i\)

Expressed as a formula: $\(\text{current\_sum} = \max(B_i, \text{current\_sum} + B_i)\)$

The overall maximum is the largest among the maximum sums at each position.

Execution Example

For \(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

The maximum value is \(3\).

Complexity

• Time Complexity: \(O(N)\)

  • \(O(N)\) to create array \(B\)
  • \(O(N)\) for a single pass with Kadane’s Algorithm

• Space Complexity: \(O(N)\)

  • \(O(N)\) to store array \(B\)
  • (Can be reduced to \(O(1)\) by computing directly without creating \(B\))

Implementation Notes

1. Due to the constraint that at least one day must be worked, we initialize max_sum to B[0] instead of \(-\infty\). This ensures the correct maximum is found even when all \(B_i\) values are negative.

2. Since daily wages \(A_i\) can have absolute values up to \(10^9\), the answer may exceed the 32-bit integer range. In Python, arbitrary-precision integers are handled automatically, so this is not an issue. However, in C++ and similar languages, long long must be used.

Source Code

def solve():
    N = int(input())
    A = list(map(int, input().split()))
    
    # Net income for each day is A_i - 1
    # Find the maximum sum of a contiguous subarray (Kadane's algorithm)
    # At least one day must be worked
    
    # Define B_i = A_i - 1, and find the maximum subarray sum of B
    B = [a - 1 for a in A]
    
    # Kadane's algorithm (must include at least 1 element)
    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()

---

This editorial was generated by claude4.5opus.