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

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.

Explanation / Answer

Algorithm for finding the sum of largest contiguos subsequence is as follows :

//max_so_far will contains the sum of largest contiguos subsequence.

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

---

---

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