Two Disjoint Runs
Problem
Given an integer array nums, choose two non-empty contiguous runs that do not overlap (the first ends strictly before the second begins).
Return the largest possible sum of the elements in both runs.
Example 1
- Input:
- nums = [2, -10, 3, 4, -20, 5]
- Output:
- 12
Runs [3, 4] and [5]: 7 + 5. [2] and [3, 4] give only 9.
Example 2
- Input:
- nums = [-3, -1]
- Output:
- -4
Both runs are forced to be single elements.
Example 3
- Input:
- nums = [3, -1, 4, -1, 5]
- Output:
- 11
[3, -1, 4] and [5], or [3] and [4, -1, 5]: 6 + 5 = 11 either way.
Constraints
- 2 ≤ nums.length ≤ 10^5
- -10^4 ≤ nums[i] ≤ 10^4
Hint
Show the first hint
Somewhere there is a boundary: the first run lies entirely at or before index i, the second entirely after it.
Walkthrough
How to approach it
01Clarify before coding
- Must both runs be non-empty? Yes, even if all values are negative.
- Can they touch (adjacent, no gap)? Yes; they just cannot share an index.
- Is the order of the runs important? No; one is to the left of the other.
02Brute force
Try every pair of runs [a, b] and [c, d] with b < c, using prefix sums for each sum.
Cost: O(n⁴) pairs (O(n²) with a smarter scan): far beyond 10^5.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.