You are given a an array A [1..n] of numbers (which can be positive, 0 or negati

Question

You are given a an array A [1..n] of numbers (which can be positive, 0 or negative). You need to design an algorithm that finds a contiguous subsequence of A with largest sum. (This is just a restatement of Problem 2(a) in Jeff Erickson's Lecture 5.) For example, given the array [- 6, 12, - 7, 0, 14, - 7, 5], the contiguous subsequence [12, - 7, 0, 14] has the largest sum, 19. (a) For 0 lessthanorequalto j lessthanorequalto n, let S (1, j) denote the largest sum of a contiguous subsequence from A [1..j], such that the contiguous subsequence includes A [j]. For 0 lessthanorequalto j lessthanorequalto n, let S (2, j) denote the largest sum of a contiguous subsequence from A [1..j]. Write down recurrences for S (1, j) and S (2, j). Make sure that you take care of all the base cases. (b) The recurrence from (a) can be implemented as a recursive function, though you don't need to do this. Now think about the memorized version of this recursive function using a 2-dimensional 2 times (n + 1) table in which the table-slot Table [i, j] is filled with S (i, j), where i Element {1, 2} and 0 lessthanorequalto j lessthanorequalto n. Figure out the order in which this table in filled and then write pseudocode for a function that finds and returns the largest sum of a contiguous subsequence of A [1..n]. (c) Write a function that takes as input A and Table (filled out using the function in (b)) and returns the optimal contiguous subsequence from A [1..n].

Explanation / Answer

(a) The recurrence can be obtained as below

base case :

S(1,1) = A[1] , since the first element has to be picked up

S(2,1) = A[1], since incase the array contains single element, it has to be picked as the only available subsequence.

Now for S(1,j) we can pick the A[j] with subsequence associated with S(1,j-1) or just A[j] depends on which ever is maximum, so it becomes

S(1,j) = max( S(1,j-1), A[j] )

for S(2,j) we can have the subsequence including A[j] which is associated with S(1,j) or without it which is associated with S(2,j-1), so it becomes

S(2,j) = max( S(1,j), S(2,j-1) )

(b) Given the above recurrences, the table can be filled starting from 1 to n as below

fill_table(A[])

{

T[1][1]=A[1];

T[2][1]=A[1];

for i =2; i<=n; i=i+1

{

T[1][i] = max (T[1][i-1]+A[i], T[i]);

T[2][i] = max (T[1][i], T[2][i-1] );

}

return T[2][n];

}

(c) The optimal solution can be tracked by the table values like from where the value T[2][n] obtained from whether T[2][n-1] or T[1][n], like wise tracking backwards we can obtain the solution

optimal_subsequence(A[],T[][])

{

i=n;

//Just iterate when T[2][i] obtained from T[2][i-1], means the number at A[i] is not part of optimal subsequence

while i>=1 && T[2][i] == T[2][i-1]

i = i-1;

//if the while breaks that means number i is part of the optimal subsequence

optimal_end_index = i;

//Again iterate untill the T[1][i] is picked up directly from A[i]

while i>= 1 && T[1][i]! = A[i]

i = i-1;

//now this when the first number is picked in the swquence

optimal_start_index = i;

//The optimal subsequence is printed below

for i = optimal_start_index; i<=optimal_end_index ; i=i+1

output A[i]

}

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

---

---

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