Consider the following so called maximum consecutive sequence problem. Given a s
ID: 3622917 • Letter: C
Question
Consider the following so called maximum consecutive sequence problem. Given asequence x1,x2,...,xn of real numbers (not necessarily positive), find a subsequence
xi,xi+1,...,xj (of consecutive elements) such that the sum xi+xi+1+...+xj is the maximum
over all subsequences of consecutive elements.
For example, for sequence 1,-3,2,-1,3,-2,2,1,-4,2, the maximum consecutive subsequence
is 2,-1,3,-2,2,1, for sequence -3,2,-3,1, the maximum consecutive subsequence is 2, and
for sequence -3,-2,-1, the maximum consecutive subsequence is the null sequence (with
sum 0).
Write an algorithm in a pseudocode to compute consecutive subsequence in linear time,
i.e. O(n) time. How the data will be represented in an algorithm?
Explanation / Answer
One way you could solve is to keep a cached for value, beginning of sequence and end of sequence. So lets say, you start with X0, and you add X1, if sum is greater than the original value, you add the next element. If you add the next element, and sum is greater then before, you move to next element and so on. Soon as you find that element you added doesn't give you greater sum, you STOP. So now, you have a sum, beginning value and next value. No, you start the same algorithm where you ended the last algorithm. And lets say you found another sequence, then you check the sum again, if the sum is larger then before, you replace current values with new values and run algorithm again. This way you only compare one value with other value, and don't have to check every sequence. I am new with cramster. HOPE THIS HELPED