TechQ: Find Maximum Value Contiguous Subsequence in Given Array

Welcome back to TechQ. Today's Question is one of the common question in dynamic programming.
TechQ: Given an input array A[1,n], Find the maximum value contiguous subsequence.

Algorithm: The solution would be trivial if all the numbers in array are greater than zero, in which case the subsequence is entire array. Below is the solution when the array also contains negative numbers.
First we will find the Maximum Sum of Subsequence ending at j in array.
Max_Sum_Ending_At(J)=Max(Max_Sum_Ending_At(J-1)+A(J), A(J));
Max_Sum_Ending_At(J) will be maximum of Max_Sum_Ending_At(J-1)+A(J) and A(J), so if Max_Sum_Ending_At(J-1)+A(J) is less than A(J) we start the sum all over again from J.

Initial value: Max_Sum_Ending_At(1)=A(1);

Once we find Max_Sum_Ending_At(J) for J=1,N. We need to find the maximum in that list which is actually the maximum value contiguous subsequence. This solution just gives the maximum value, to know the sub-array you just need to maintain the back pointers.

Complexity: O(N)
Example:
Lets take array A={1,5,-8,5,7,-10,8,9,-6,9}
Max_Sum_Ending_At(1)=1;
Max_Sum_Ending_At(2)=max(1+5,5)=6;
Max_Sum_Ending_At(3)=max(6+-8,-8)=-2;
Max_Sum_Ending_At(4)=max(-2+5,5)=5;
Max_Sum_Ending_At(5)=max(5+7,7)=12;
Max_Sum_Ending_At(6)=max(12+-10,-10)=2;
Max_Sum_Ending_At(7)=max(2+8,8)=10;
Max_Sum_Ending_At(8)=max(10+9,9)=19;
Max_Sum_Ending_At(9)=max(19-6,-6)=13;
Max_Sum_Ending_At(10)=max(13+9,9)=22;
Maximum among all the numbers is 22 and sub array is A[4,10].

Feel free to let us know any interesting questions that needs to be covered in TechQ