Show problems as
Classic problem #3026MediumArrayHash TablePrefix Sum

Maximum Good Subarray Sum

Real-world version: Best Matched Block of Ledger Entries
Tracked in this browser only
Read Maximum Good Subarray Sum on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A ledger holds the signed amounts of a day's entries in the list entries; a credit is positive and a debit is negative.

An auditor works on matched blocks. A matched block is a run of consecutive entries in which the amount of the first entry and the amount of the last entry differ by exactly gap, in either direction. Because gap is at least 1, a matched block always holds at least two entries.

Return the largest total a matched block can have. Return 0 when the ledger has no matched block at all; note that a matched block whose entries happen to total exactly 0 produces the same return value, so the two situations cannot be told apart from the answer alone.

Examples

Example 1

Input
entries = [3, 9, 3, 9], gap = 6
Output
24

The whole ledger is a matched block: it starts at 3, ends at 9, and those differ by 6. Its total is 24.

Example 2

Input
entries = [4, -100, 6, -100, 4], gap = 2
Output
-90

Entries 1 to 3 form a matched block, running 4, -100, 6, since 4 and 6 differ by 2, and it totals -90. Entries 3 to 5 also form one and also total -90.

Example 3

Input
entries = [7, 3], gap = 5
Output
0

The only run of two or more entries starts at 7 and ends at 3, which differ by 4 rather than 5, so there is no matched block and the answer is 0.

Constraints

  • 2 <= entries.length <= 10^5
  • -10^9 <= entries[i] <= 10^9
  • 1 <= gap <= 10^9
  • Every block total the ledger can produce is between -10^14 and 10^14.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def best_matched_block(entries: list[int], gap: int) -> int:
Java
public long bestMatchedBlock(int[] entries, int gap)

More on the same topics