[10pts] Let S subsequence SM = (ai, ai+1, .. numbers in SM is maximum over all subsequences of S. Note that the sum is assumed to be O if the subsequence is empty. Your algorithm should run in O(n)...

Let S = (a1a2; : : : an) be a sequence of integers. Design an algorithm to  nd the
subsequence SM = (ai; ai+1; : : : ; aj) of S, with consecutive elements, such that the sum of the
numbers in SM is maximum over all subsequences of S. Note that the sum is assumed to be
0 if the subsequence is empty. Your algorithm should run in O(n) time.

Extracted text: [10pts] Let S subsequence SM = (ai, ai+1, .. numbers in SM is maximum over all subsequences of S. Note that the sum is assumed to be O if the subsequence is empty. Your algorithm should run in O(n) time. (a1a2, ... an) be a sequence of integers. Design an algorithm to find the ., a;) of S, with consecutive elements, such that the sum of the