Show problems as
Classic problem #53MediumArrayDynamic ProgrammingDivide and Conquer

Maximum Subarray

Real-world version: Best Trading Day Run
Tracked in this browser only
Read Maximum Subarray on LeetCode(opens in a new tab)

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

Learn the pattern firstDivide & Conquer · Recursion, animated step by step

A market stall balances its books every evening. daily[i] is the money the stall cleared on day i: a positive figure on a day it came out ahead, a negative figure on a day it went backwards, and 0 on a day that broke even.

The owner wants to quote her strongest run of trading. A run is the days from some day i through some day j with i <= j, taken back to back with no days left out in between, and its worth is the sum of the figures on those days. Return the worth of the strongest run in daily.

A run must contain at least one day; skipping every day is not allowed. So when the stall went backwards on all of its days, the strongest run is the single day it lost the least on, and the answer you return is negative. Do not report 0 for that case.

Examples

Example 1

Input
daily = [3, -2, 7, -8, 4]
Output
8

Days 0 through 2 clear 3 - 2 + 7 = 8. Taking day 2 by itself yields only 7, and carrying on into day 3 gives back 8 of it, so no other run beats 8.

Example 2

Input
daily = [-6, -2, -9]
Output
-2

Every run of two or more days is worse than its own worst day, so the strongest choice is day 1 alone at -2. Since a run cannot be empty, a negative answer is the correct one.

Example 3

Input
daily = [5]
Output
5

One day of trading means exactly one run is available and its worth is 5.

Constraints

  • 1 <= daily.length <= 10^5
  • -10^4 <= daily[i] <= 10^4

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_run_total(daily: list[int]) -> int:
Java
public int bestRunTotal(int[] daily)

More on the same topics