Task

Given a sequence of integers, find a continuous subsequence which maximizes the sum of its elements, that is, the elements of no other single subsequence add up to a value larger than this one.



An empty subsequence is considered to have the sum of   0;   thus if all elements are negative, the result must be the empty sequence.




function [S,GS]=gss(a)
% Greatest subsequential sum 
a =[0;a(:);0]';
ix1 = find(a(2:end) >0 & a(1:end-1) <= 0);
ix2 = find(a(2:end)<=0 & a(1:end-1) > 0);
K = 0;
S = 0;
for k = 1:length(ix1)
	s = sum(a(ix1(k)+1:ix2(k)));
	if (s>S) 
		S=s; K=k;
	end;
end; 
GS = a(ix1(K)+1:ix2(K));
 