Weighted Interval Scheduling & Dynamic Programming (Knapsack, Edit Distance) Suppose you are in the middle of a pandemic. Given a list of daily case counts to analyze, one would like to identify...

Weighted Interval Scheduling & Dynamic Programming (Knapsack, Edit Distance)

Suppose you are in the middle of a pandemic.

Given a list of daily case counts to analyze, one would like to identify periods of high growth in the cases.

One way to do is to look at the change in new cases from day to day. For example, suppose we have the following data: (picture)

We would like to identify the period of maximal growth. In the case above, such a period would be from Days 3 through 6, which has net growth of 47 cases.

Give an algorithm in pseudocode that, when given a list of daily "changes" in case rates, identifies the period of maximal growth. Give proofs of correctness and running time for your algorithm.