45 -34 8 7 48 -30
45 -34 8 7 48 <- max 55
45 -34 8 7 <- here I find the 63
45 -34 8 <- max 45
45 -34 <-max 74
45 <- max 74
45 11 19 26 74 44
(apply
max
(flatten
(for
[i (range (count v))]
[(apply + (take i v)) (apply + (drop i v))]))))
(apply
max
(flatten
(for
[i (range (count v))]
[(apply + (take i v)) (apply + (drop i v))]))))
int rstart = 0;
int rend = 0;
int maxsum = 0;
int csum = 0;
int start = 0;
for(int current = 0; current < size; ++current){
csum += data[current];
if(csum < 1){
start = current+1;
csum = 0;
}else if(csum > maxsum){
rstart = start;
rend = current;
maxsum = csum;
}
}
# 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)
original_length = sets.length
(sets.length-3).step(0, -2) do |i|
left, neg, right = sets[i], sets[i+1], sets[i+2]
if [left[1], right[1]].min + neg[1] > 0
sets[i] = [(left[0].first…right[0].last), left[1] + neg[1] + right[1]]
sets.delete_at(i+2)
sets.delete_at(i+1)
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
nil while merge! sets
# We have our maxima. Return the largest of our remaining regions.
sets.reduce {|a, x| x[1] > a[1] ? x : a}
end
Given a vector of floating-point numbers, find the largest sum among the contiguous subvectors.
So for example, in the vector x
[45 -34 8 7 48 -30]
The contiguous subvector with the largest sum is x[2…4] totaling 63.
Now this problem would not be so interesting but for the story behind it. The author tells a story that the original algorithm the programmer came up with was going to take 15 days to process a vector of 100,000 numbers (note that this book is relatively old).
However, redesigning the algorithm brought the time down to 5 milliseconds.
So, your challenge, if you choose to accept it, is to try your hand at solving this problem.
At the end of this post you'll find a vector of 5000 random numbers to use. We can make it bigger if necessary.
Time your tests and post the results in the thread. Any language is acceptable. I encourage multiple attempts to make it faster. If you wish, refrain from reading the thread until you post your solution, but if you want to see other people's attempts first feel free.
Good luck!