Overview

Since working on each day yields a profit of \(A_i-1\) yen, this problem asks us to find the “maximum contiguous subarray sum” of the array \(B_i=A_i-1\).

Analysis

The effective income when working consecutively from day \(i\) to day \(j\) is
$\((A_i+\cdots+A_j)-(j-i+1)\)\( but since this simply subtracts \)1\( yen per day, it is equivalent to: \)\( (A_i-1) + (A_{i+1}-1) + \cdots + (A_j-1) \)$

In other words, if we define \(B_i = A_i - 1\), then what we want to find is: - The maximum sum of a contiguous subarray of array \(B\)

Why a naive approach doesn’t work

If we try all intervals \((i,j)\) and compute their sums, there are approximately \(N^2/2\) intervals.
For \(N \le 2\times 10^5\), an \(O(N^2)\) approach will not run in time (TLE).

How to solve it

By maintaining “the maximum subarray sum ending at the current position” through a single scan, we can find the maximum subarray sum in \(O(N)\) (Kadane’s algorithm).

Example: For \(A=[3,1,2]\), we get \(B=[2,0,1]\)
The maximum contiguous subarray sum is \(2+0+1=3\), so the answer is \(3\).

Algorithm

We use Kadane’s algorithm (a type of dynamic programming).

• Process \(x = A_i - 1\) sequentially
• cur: the maximum income of a contiguous interval ending at day i
• best: the maximum income found so far

The updates are as follows:

• Start a new interval beginning at day i: \(x\)
• Extend the previous interval by adding day i: \(\text{cur}+x\)

Therefore: $\(\text{cur} = \max(x, \text{cur}+x)\)\( \)\(\text{best} = \max(\text{best}, \text{cur})\)$

Also, since we must work at least 1 day, we cannot initialize with an empty interval (sum of 0). We initialize both cur and best with the first element \(A_1-1\).

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(1)\) (constant aside from the input array)

Implementation Notes

• Initialization is important: Since we must select at least one day, set best = cur = A[0]-1 (do not initialize with 0).

• Each element can be up to about \(10^9\), and \(N\) is large, so the sum can reach around \(10^{14}\), but Python’s integers handle this safely.

• Since the input is large, using sys.stdin.buffer.read() is faster.

  Source Code

import sys

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    a = list(map(int, data[1:1+n]))

    best = cur = a[0] - 1
    for i in range(1, n):
        x = a[i] - 1
        cur = max(x, cur + x)
        best = max(best, cur)

    print(best)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.