$***1.$ A contiguous subsequence of a sequence $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. On input a list of numbers, $x_1,x_2,$cdots,$x_n,$ design a linear time algorithm to output the contiguous subsequence with maximum sum. For the preceding example, the answer would be $10,-5,40,10,$ with a sum of $55.$

$($Hint: For each $j,1jn,$ consider contiguous subsequences ending exactly at position $j.)$