Optimize algo to Calculate of substring with max total

What will be the optimize/Smart algo to get the max total sub-sequence from following series of 'n' numbers Example:

Input:             Index   0  1  2  3  4  5  6  7 
                   Series -1  0  3 -2  5 -2  6  1

trials  :          start :4 end :7 total :10
                   star开发者_运维百科t :6 end :7 total :7


Output (Max Total Sub-sequence):  start :2  ,end:7 , total:11 

You can implement an O(n) algorithm easily; There are two ways I can think of:

1) DP:

Let dp[i] be the length of the maximum subsequence ending at element i then dp[0] = element[0]. And for each i, dp[i] = max( dp[i - 1] + element[i], element[i] ). That's because you have two choices, either adding the current element to the previous maximal subsequence, or creating a new one. Take the maximum over all i's, and that's your answer. You can find the beginning and end by tracking the changes easily.

2) A simple intuitive algorithm:

First of all, create a prefix sum array, so that prefix[i] is the sum of the elements 0...i. Now if you have a subsequence from a to b, then its sum is obviously prefix[b] - prefix[a - 1] ( a = 0 is a special case that can be handled easily ). Now suppose we fixed b, then the optimal choice should minimize prefix[a - 1]. So we can iterate over all i's, keeping the minimum prefix[j] so far. The answer is just the maximum over all steps, at each step: prefix[i] - prefix[j].

Here's pseudocode:

// Compute prefix sum array easily and trivially ( ask me if you want how )

int curMin = 0, answer = - INFINITY;

for i = 0 to n - 1

      answer = max( answer, prefix[i] - curMin );

      curMin = min( curMin, prefix[i] );

A linear algorithm exists. See for example this http://wordaligned.org/articles/the-maximum-subsequence-problem