# If there's only one entry, return it, whether it's positive or negative.
return sets[0] if sets.length == 1
# Remove negatives from the front and back.
trim! sets
# Isolate regions of positive and negative numbers
def partition (v)
sets = []
left = 0
i = 1
v.each_cons(2) do |l, r|
# are the signs different?
if (l >= 0) != (r >= 0)
sets.push [(left…i), v[left…i].reduce {|a, n| a + n}]
left = i
end
i += 1
end
sets.push [(left…i), v[left…i].reduce {|a, n| a + n}]
end
# Remove negative regions from the front and back - they'll never be included.
def trim! (sets)
sets.shift if sets.first[1] < 0
sets.pop if sets.last[1] < 0
end
# Merge adjacent regions of positive over a lesser region of negative.
def merge! (sets, distance)
distance = distance * 2 + 1
original_length = sets.length
i = 0
while i + distance <= sets.length
nums = sets[i…i+distance]
sum = nums.reduce(0) {|a, n| a + n[1]}
max = nums.reduce(0) {|a, n| n[1] > a ? n[1] : a}
if sum >= max
sets[i…i+distance] = [[(nums.first[0].first…nums.last[0].last), sum]]
else
i += 2
end
end
sets.length != original_length
end
def calculate (v)
# Partition the vector into regions by sign.
sets = partition v
# If there's only one entry, return it, whether it's positive or negative.
return sets[0] if sets.length == 1
# Remove negatives from the front and back.
trim! sets
# If there's only one now, it's the only positive island, so return it.
return sets[0] if sets.length == 1
# Iteratively merge adjacent regions to create larger regions
distance = 1
while distance*2 + 1 <= sets.length
nil while merge!(sets, distance)
distance += 1
end
# We have our maxima. Return the largest of our remaining regions.
sets.reduce {|a, x| x[1] > a[1] ? x : a}
end
(defn kadane [v]
(loop
[x v
max-ending-here 0
max-so-far 0]
(if (seq x)
(recur
(next x)
(max 0 (+ max-ending-here (first x)))
(max max-ending-here max-so-far))
max-so-far)))
int rstart = 0;//start index of max range
int rend = 0;//end index of max range
int maxsum = 0;//max sum found so far
int csum = 0;//current sum of the working range
int start = 0;//start index if working range
for(int current = 0; current < size; ++current){//scan through the array
csum += data[current];//add current element to current sum
if(csum < 1){//is the working range no longer contributing?
start = current+1;//set new working range start to next element index
csum = 0;//clear working sum
}else if(csum > maxsum){//is this a new overall max?
rstart = start;//set the new max range and sum
rend = current;
maxsum = csum;
}
}
program LCS;
#include( "stdlib.hhf" )
static
data: int32[5000] := [336,502,-557,-371,507,…array ellided…,213,42,-253,450];
begin LCS;
mov(0,eax); // greatest sum so far
mov(0,ebx); // temp sum
mov(0,edi); // sum start index
mov(0,esi); // array index
mov(0,ecx); // final start index
mov(0,edx); // final end index
top:
add(data[esi*4],ebx);
jns positive;
mov(esi,edi);
inc(edi);
mov(0,ebx);
positive:
cmp(ebx,eax);
jng next;
mov(edi,ecx);
mov(esi,edx);
mov(ebx,eax);
next:
inc(esi);
cmp(esi,5000);
jb top;
done:
stdout.puti32(ecx);
stdout.put("-");
stdout.puti32(edx);
stdout.put(nl);
stdout.puti32(eax);
stdout.put(nl);
end LCS;
max_ending_here = max(0, max_ending_here + x)
It's clear you have a winning approach. I wouldn't worry about finishing it unless someone was paying me for it :)