The best run of the season
- O(n²) · Very hard
- Full plan
- Python
- JavaScript
- lists
- loops
Problem
"One game on its own tells you nothing; it's the run that counts," the radio commentator likes to say. He has the goal difference of every game of the season, in order: 2 if his team won by two, -1 if it lost by one, 0 for a draw. He wants the stretch of back-to-back games that added up the most.
Write a function that takes that list of whole numbers (never empty) and returns, as a whole number, the largest sum of a stretch of consecutive games. A stretch has at least one game and can go from a single game to the whole season, but you cannot skip games in the middle.
With [2, -3, 4, -1, 2, -5, 3], the best stretch is 4, -1, 2: you return 5. If every game is negative, the best stretch is the least bad game: with [-4, -2, -7] you return -2, not 0.
Examples
The example
[2, -3, 4, -1, 2, -5, 3] → 5
Nothing but wins
[1, 2, 3] → 6
Worth crossing the losses
[3, -1, -1, 4] → 5
A single game
[7] → 7
Besides these, the challenge has hidden tests that are revealed when you submit your solution.
You start with this
Python
def best_run(games):
passJavaScript
function bestRun(games) {
}It opens in your browser, with the editor and the tests. This challenge is part of the full plan; the O(1) and O(log n) ones are free.