(Solved): Problem 1 Let S=(s_(1),s_(2),cdots,s_(n)) be a sequence of n numbers. A "contiguous subsequence" of ...

Problem 1 Let

be a sequence of

numbers. A "contiguous subsequence" of

is a subsequence

(for some

), which is made up of consecutive elements of

. (For example, if ), then

is a "contiguous subsequence", but

is not.) Given a sequence

, our objective is to find a contiguous subsequence whose sum if maximized. (For example, if

, such a contiguous subsequence would be

, whose sum is 59 .) Our "Maximum-Sum Contiguous Subsequence Problem" is defined as follows: Input: A sequence of numbers

. Output: A contiguous subsequence of

whose sum is maximized. Your task: Design an algorithm of time complexity

for the above problem. (Remember: as we emphasized in class, whenever you design an algorithm, you need to: (1) explain the main idea of the algorithm, (2) present its pseudo-code, (3) prove its correctness, (4) analyze its time complexity. For dynamic programming, (1) and (3) can often be the same.) (Hint: For each

, consider contiguous subsequences ending exactly at position

.)