Problem 2 Top earnings

You manage a hedge fund. Suppose you are given an array of numbers a1, . . . , an that summarizes a trader’s earnings (or losses) for n days. Your goal is to present a dynamic programming algorithm that computes the most lucrative trading period for this trader; i.e., your algorithm must find the pair (i, j) where i ≤ j that maximizes the sum s = ∑ j k=i ak . The algorithm should output (i, j,s) and run in Θ(n) time.

(a) Define a variable bestn in the style of DP solutions that can help solve this problem. Use sentences to explain what the variable represents.

(b) Provide an equation that defines this variable.

bestn =

(c) Provide pseudo-code for a Θ(n)-time algorithm. Prove your algorithm correct and analyze its running time. (Assume additions are O(1)-time operations.) Your pseudo-code should require < 20 lines in total and should output (i, j,s).