Homework 8 Maximum Profit problem

1 Maximum Profit
 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.