Problem 3: Radio Commercials

https://open.kattis.com/problems/commercials/

Given a list of profits at each hour, calculate the maximum profit that you can from some continuous sequence of commercial breaks.

First, note that at each hour,

net income = (# of students at each hour) - (price of commercial break)

At each hour, the two options are:

1. Play the commercial.

2. Don't play the commercial, which ends a continuous sequence of commercial breaks.

We can use an listA to keep track of the positive gain over the sequence of commercial breaks, and find the maximum possible gain.

If the current gain (sum of incomes over continuous period) is negative at a certain hour i, then including this hour in our operating time will not maximize the profit. Thus, negative gain is a criterion for not playing the commercial. We set A[i] = 0, which ends a continuous subsequence of operating hours.

Otherwise, A[i] = A[i - 1] + NetIncome[i]. This is the possible (nonnegative) gain at each hour.

The maximum possible profit will be $max_i {A[i]}$ .