Solution Found!
A contiguous subsequence of a list S is a subsequence made up of consecutive elements of
Chapter 6, Problem 6.1(choose chapter or problem)
A contiguous subsequence of a list \(S\) is a subsequence made up of consecutive elements of \(S\). For Instance, if \(S\) is
\(5,15,-30,10,-5,40,10\)
then \(15,-30,10\) is a contiguous subsequence but \(5,15,40\) is not. Give a linear-time algorithm for the following task:
Input: A list of numbers, \(a_{1}, a_{2}, \ldots, a_{n}\).
Output: The contiguous subsequence of maximum sum (a subsequence of length zero has sum zero).
For the preceding example, the answer would be \(10,-5,40,10\), with a sum of \(55\).
(Hint: For each \(j \in\{1,2, \ldots, n\}\), consider contiguous subsequences ending exactly at position \(j.\))
Questions & Answers
QUESTION:
A contiguous subsequence of a list \(S\) is a subsequence made up of consecutive elements of \(S\). For Instance, if \(S\) is
\(5,15,-30,10,-5,40,10\)
then \(15,-30,10\) is a contiguous subsequence but \(5,15,40\) is not. Give a linear-time algorithm for the following task:
Input: A list of numbers, \(a_{1}, a_{2}, \ldots, a_{n}\).
Output: The contiguous subsequence of maximum sum (a subsequence of length zero has sum zero).
For the preceding example, the answer would be \(10,-5,40,10\), with a sum of \(55\).
(Hint: For each \(j \in\{1,2, \ldots, n\}\), consider contiguous subsequences ending exactly at position \(j.\))
ANSWER:Step 1 of 3
To find the contiguous subsequence of maximum sum, loop through the given list and keep track of the maximum sum you got so far and maximum sum among positive segments of the list. On getting a positive sum, compare it with the maximum sum you got so far. And update the maximum sum accordingly.