Maximal Contiguous Subsequent Sum Problem

Problem:

Maximum Contiguous Subsequence Sum:  given (a possibly 
negative) integers A1, A2, …, AN, find (and identify the 
sequence corresponding to) the maximum value of  
∑
=
j
k i
Ak         
For the degenerate case when all of the integers are negative, 
the maximum contiguous subsequence sum is zero. 



Solution:

• Initialize start=0,end=0,max=0,S=0,tmpstart=0
• Loop over all the elements of array
•  if S > max  then assign max=S,end=currentindex,start=tmpstart
• if  S < 0 (that means we can omit all values calculated so for) then assign S=0,tmpstart=i+1
• tmpstart represents temporary start index which is used to store the start index of current subarray.
• then print max,end and start index.

Complexity: O(n)


Code: