Maximum contiguous subsequence

Given an array of N numbers (positive, zero, negative), find maximum contiguous subsequence i.e. a subsequence which is contiguous and which has maximum sum i.e. mathematically, sum of k elements A[k] where k ranges from i to j, such that 0<=i<=j<=N-1, is maximized.

Let's take an example. If A is {2,4,1,5,6,7}, well! the answer is the whole array itself. And that's why we need to consider a generalized case in which the array contains positive as well as negative elements. Similarly, for the array A={-2,-10,-9,-1}, the sum better be zero than negative and the the answer is empty subsequence. Thus, these two are degenerate cases.

Now, let's consider the general case. We can come up with a trivial algorithm as follows. We want to find a subsequence of the form 0<=i<=j<=N-1, thus we can straightaway write 2 loops as follows.

for i=0 to N-1
       for j=i to N-1
             keep sum of A[i] through A[j], keep track of max sum seen so far and corresponding i and j values
       end for
end for

As one can see, this is O(N^3) algorithm. If you think it's O(N^2), please take a look at the step in which we compute the sum. This sum needs to be computed over all subintervals and thus it causes another for loop, giving rise to the complexity of O(N^3).

Now, of course the question is - Can we do better? We can definitely do this in O(N^2) as you must have realized by now. (I took quite a lot of time to get to this :D) Basically, we can eliminate the innermost loop over K using following fact. If we denote sum of A[i] through A[j] as Sum(i,j) then we can write
       sum(i,j+1) = sun(i,j)+A[j+1]
Thus, we need not go through all values again and we save one loop here, thus getting O(N^2) complexity.

We can still do better btw! At this moment I myself asked a question - how much better? Can we go sub linear? And I think, we cannot. The reason is - as the input array is not sorted or in any order, we cannot judge for more elements based on small number of elements. Remember what we do in binary search - comparison with one element at the middle (small number of elements) gives us an indication of half of the array (more number of elements) being useless for further steps. Such indication we cannot get here and thus we HAVE TO look at EVERY element at least once and as we will see - also at most once! Thus, we cannot hope for sub linear complexity but it has to be linear.

The algorithm, which I am not writing here is of the complexity O(N). It can be arrived at by two different methods. The underlying principle is the same for both the methods. The hints for the two methods are as follows. I think, if you get one of them, the other one will be trivial.
1. Biggest hint for method 1: The array contains negative elements too and any negative sum is worse than sum=0
2. If you have solved this by method 1, then this hint may be redundant: Use dynamic programming

nJoy!! :)