Given a list of summable things, the maximum segment sum is highest value given by summing all the elements of a contiguous group of items. In this problem, you'll have to find the highest value given by the sum of all the elements of a non-contiguous subsequence of the original list.
- There are no non-contiguous subsequences of a list with two or fewer elements (duh!);
- A non-contiguous subsequence is still a sequence, but which has at least one of the constituting elements originally not contiguous to the others (left or right);
- As long as the elements are summable, there are no additional constrains;
- Lists are finite.
mncss [-4,-3,4] returns 0 (given by [-4,4])
mncss [-4,-3,-7,2,1,-2,-1,-4] returns 2 (given by [2,1,-1])
mncss [1,2,3,4] returns 8 (given by [1,3,4])
mncss [2,4] is an invalid input with non-specified output
mncss l=maximum$sum<$>(subsequences l\\(inits l>>=tails))mncss l=maximum$map sum(subsequences l\\(inits l>>=tails))mncss x=maximum[sum y|y<-subsequences x,not$isInfixOf y x]mncss=liftA2(\\)subsequences(tails>=>inits)>>>maximum.map summncss x=maximum$map sum[y|y<-subsequences x,not$isInfixOf y x]mncss(x)=maximum(sum(x[s]) for s=subsets(1:length(x)) if any(≠(1),diff(s)))s=lambda l:max(l)if max(l)<0else sum([max(x,0)for x in l])
mncss=lambda l:max([s(l[:i])+s(l[i+1:])for i in range(1,len(l)-1)])s=lambda l:[l[i:j] for i in range(len(l)+1) for j in range(i,len(l)+1)]
mncss=lambda l:max([sum(x) for x in [list(x) for i in range(len(l)+1) for x in c(l,i)] if x not in s(l)])