1 Maximum Profit
Do problem 7 of Chapter six (page 318). This is called Maximum Profit problem in class, where we show an O(nlogn) time algorithm. Briefly, in this problem, you are given stock prices p(i) for day i for each of n days. The objective is finding two days: day j and day i where j < i such that p(i) − p(j) is maximized over all choices of j and i.
Now give an O(n) time algorithm for this problem.
2 Maximum consecutive subarray
You are given a sequence S of integers (not necessarily positive). The number of integers is n. The problem is to find the consecutive subsequence of S with maximum sum. Here, “Consecutive” means that you are not allowed to skip numbers. For example if the input was 12, −14, 1, 23, −6, 22, −34, 13 the output would be 1, 23, −6, 22.
Now give a linear time dynamic programming algorithm for this problem.
You should explain why a naive recursive solution is not possible. That is, figure out why knowing the i-th number, and the maximum consecutive sum of the first i − 1 numbers, is not enough to compute the maximum consecutive sum of the first i numbers. This should give you a big hint how to strengthen the inductive hypothesis.
3 Interleaving strings
Do problem 19 of Chapter six (page 329). Briefly, in this problem, you are given three strings s, x and y. The goal is deciding whether s is an interleaving of x and y. We say s is an interleaving of x and y if symbols in s can be partitioned (not necessiarliy contiguously) into two subsequences s0 and s00 such that s0 is repetition of x and s00 is repetition of y.
Now give a polynomial time algorithm for this problem, which takes strings s, x and y and decides if s is an interleaving of x and y.
4 Exercise 24 (p.331)
Do problem 24 of Chapter six on page 331.
