3. You are given an array A[1..n] containing numbers (not necessarily integers),

Question

3. You are given an array A[1..n] containing numbers (not necessarily integers), which can be positive or negative or zero. This problem has you construct a dynamic programming algorithm, running in O(n) time, that finds indices q and p, n p > q 1 such that A[p] A[q] is maximum. Assume n 2.

(a) Let OP T(j) denote the maximum difference A[p] A[q], where j p > q 1. Write a recurrence expressing OP T(j) in terms of OP T(·) for smaller subproblems. Hint: As we have seen in some examples of dynamic programming solutions, you may need to define another (related) problem, whose solution may also participate in the recurrence. Make sure you write the recurrence relation for this related problem as well.

(b) Using your recurrence explain (in pseudocode or in plain English) how one can solve the above problem in O(n) time.

Explanation / Answer

Another problem which we can use to solve this is maximum sum subarray

So this gives OPT(j) = max(OPT(j) - OPT(j-1), OPT(j))

b)

Pseduo code

Pseduo code for Kadane's Algorithm (using from wiki paedia as this is a well known algorithm which would have been taught in class)

Related Questions

Navigate

• Browse (All)
• Browse 3
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.