Food Truck Best Stretch

Easysliding windowAlso known as Maximum Sum Subarray of Size K

You run a food truck and keep a log of each day's profit. Rainy days, broken fryers and festival fees mean some days lose money, so the log has negative numbers too.

A magazine wants to feature your truck and asks for your best run of exactly k days in a row. You want to know the highest total profit any k consecutive days in your log reached.

Your task

Write bestStretch(profits, k). Return the largest sum of any k consecutive entries of profits.

The answer can be negative if every stretch of k days lost money.

bestStretch(profits: int[], k: int) → int

Examples

Example 1

Input

profits = [120, -40, 300, 80, -200, 150]
k = 3

Output

Why

The 3-day stretches add up to 120 - 40 + 300 = 380, then -40 + 300 + 80 = 340, then 300 + 80 - 200 = 180, then 80 - 200 + 150 = 30. The best is 380, from the first three days.

Example 2

Input

profits = [-50, -20, -90, -10]
k = 2

Output

-70

Why

Every 2-day stretch lost money: -70, -110, -100. The best is -70. If you start your running best at 0, you would wrongly answer 0.

Constraints

1 ≤ k ≤ profits.length ≤ 10,000
-10,000 ≤ profits[i] ≤ 10,000

Start with brute force

For every starting day, add up the next k profits, and keep the largest total.

That is about n × k additions. With 10,000 days and k = 5,000 it is roughly 25 million additions, almost all of them repeated: neighbouring stretches share k - 1 days, and you add those same days up again every time.

Hints

0 of 4 shown

Hint 1
In the first example, the stretch of days 0 to 2 sums to 380. The next stretch is days 1 to 3. Which days do the two stretches share?
Hint 2
Two neighbouring stretches share all but one day at each end. Moving one day to the right drops the oldest day and adds one new day.
Hint 3
So you never need to add up k numbers again. You can update the previous total with one subtraction and one addition.
Hint 4
Sum the first k days and make that your best so far. Then for each next day i, add profits[i], subtract profits[i - k], and keep the largest total you see.

Walkthrough and solution

Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.

How to solve it

Think of a frame exactly k days wide lying on the log. Sliding it one day to the right lets one day in on the right and pushes one day out on the left. Everything in between stays, so the total changes by just those two days.

Trace [120, -40, 300, 80, -200, 150] with k = 3:

First frame, days 0 to 2: 120 - 40 + 300 = 380. Best = 380.
Slide: add day 3 (80), drop day 0 (120). 380 + 80 - 120 = 340. Best stays 380.
Slide: add day 4 (-200), drop day 1 (-40). 340 - 200 + 40 = 180. Best stays 380.
Slide: add day 5 (150), drop day 2 (300). 180 + 150 - 300 = 30. Best stays 380.

Each slide costs two operations, whatever k is. Start best at the first frame's total, not at 0, so an all-losing log still gives the right answer.

Reference solution

function bestStretch(profits, k) {
  let total = 0;
  for (let i = 0; i < k; i++) total += profits[i];
  let best = total;
  for (let i = k; i < profits.length; i++) {
    total += profits[i] - profits[i - k]; // add the new day, drop the oldest
    best = Math.max(best, total);
  }
  return best;
}

def best_stretch(profits, k):
    total = sum(profits[:k])
    best = total
    for i in range(k, len(profits)):
        total += profits[i] - profits[i - k]  # add the new day, drop the oldest
        best = max(best, total)
    return best

TimeO(n)k additions for the first frame, then two operations per slide.

SpaceO(1)Just the running total and the best total.

Learn the idea: Sliding Window Prefix Sums

Ctrl+Enter runs

Run your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.

Write code