A. Define the entries of your table in words. E.g. T(i) or T(i, j) is...

B. State recurrence for entries of the table in terms of smaller subproblems.

C. Write PSEUDOCODE for your algorithm to solve this problem.

D. Analyze the running time of your algorithm in Big O( ).

Given two sequences of n numbers: X = 21, 22, ..., Xn and Y = 41, 42, ..., Yn. We want to find the sequence Z = z1,..., Zk which appears as a substring of X and Y, and which has maximum sum. Design a dynamic programming algorithm for this problem. You only need to output the maximum sum, you don't need to output the substring. For example, for the following input: = 5, 2, 7, -1,6, -4,9, 2, -3,1 Y = 7,-1, 6, -4,5,5, 1,-1,9, 2 then the answer is 12 (using substring 7,-1,6). (Faster (and correct) in asymptotic 0c) notation is worth more credit.)