Box Office Campaign Forecasts
Maximum contiguous subarray sum, or zero, for each array prefix
A theater is planning a promotional campaign across its scheduled performances. The array gains gives the projected net gain from including each performance in the campaign, in schedule order. A negative value means the promotion would cost more than it earns for that performance.
A campaign must cover one contiguous block of performances. The theater may also choose not to run a campaign, for a net gain of 0.
For each index i, consider only performances from index 0 through index i. Find the largest net gain achievable by a campaign entirely within that prefix.
Return an integer array forecasts of the same length as gains, where forecasts[i] is that largest net gain. Return an empty array if there are no performances.
Examples
Example 1
Input: gains = [4,-6,5,2] Output: [4,4,5,7]
For gains [4, -6, 5, 2], the first performance is the best campaign in each of the first two prefixes. In the third prefix, the third performance alone is better. In the final prefix, combining the third and fourth performances is best.
Example 2
Input: gains = [-3,-1,-4] Output: [0,0,0]
Every performance in [-3, -1, -4] has a negative projected gain, so choosing no campaign is best for every prefix.
Example 3
Input: gains = [2,-1,3] Output: [2,2,4]
For [2, -1, 3], the first performance remains the best choice after the second performance is added. Once the third is available, using all three performances is best.
Constraints
- 0 <= gains.length <= 10000
- -1000000 <= gains[i] <= 1000000
- All gains are integers.
Choosing no campaign is always allowed. Only the maximum gain is returned, so ties between campaigns do not affect the answer. Totals may exceed a signed 32-bit integer.
Hints
Show hint 1Hint 1
Track the best gain of a campaign that ends at the current performance. Can a negative gain from the previous prefix ever help?
Show hint 2Hint 2
The best campaign anywhere in the current prefix is either the previous prefix's best campaign or a campaign ending at the current performance.
Follow-up questions
What an interviewer might ask once you have a working solution.
- Can you compute the forecasts in one pass using constant auxiliary space, excluding the returned array?
- How would you also return each prefix's best campaign boundaries, preferring the shortest campaign and then the earliest start when gains tie?
Practice this with an AI interviewer
Explain your approach out loud, write Python or JavaScript, run it against hidden tests (including large inputs), and get a scored debrief.
Start this problem