Maximum Total Subarray Value I
Real-world version: Repeatable Trading WindowsThe statement here is our own: the same inputs, outputs and technique.
prices holds one settlement price per trading day, in day order. A window is any non-empty run of consecutive days, and the spread of a window is its highest settlement price minus its lowest.
A desk must file exactly k windows for the quarter. The same window may be filed more than once, and there is no rule against overlapping windows. The quarter's score is the sum of the spreads of the k filed windows.
Return the largest score the desk can file.
Examples
Example 1
- Input
- prices = [3, 1, 4], k = 3
- Output
- 9
The window covering all three days has highest price 4 and lowest price 1, a spread of 3. Filing that window three times scores 9.
Example 2
- Input
- prices = [1, 5, 2, 6], k = 2
- Output
- 10
The window covering all four days has highest price 6 and lowest price 1, a spread of 5, and filing it twice scores 10.
Example 3
- Input
- prices = [0, 1000000000], k = 100000
- Output
- 100000000000000
The record has highest price 1000000000 and lowest price 0, so the two-day window spreads 1000000000, and filing it 100000 times scores 100000000000000.
Constraints
- 1 <= prices.length <= 5 * 10^4
- 0 <= prices[i] <= 10^9
- 1 <= k <= 10^5
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.
def max_total_spread(prices: list[int], k: int) -> int:public long maxTotalSpread(int[] prices, int k)Checking your plan…
How this problem was checked
- Passed: Reference solution run against 12 test cases: 12 passed
- Passed: 3 worked examples confirmed by running the code
- Passed: 0 eight-word sequences shared with the parent problem's text
- Passed: Agrees with an independent brute-force solution on random inputs
- Passed: Test set shown to catch deliberately broken solutions
- Passed: Reviewed by a separate quality pass
- Passed: Function arity matches the parent problem's