bvbellomo
BAN USERIf there are 2 elements in the array, or all the elements are zero, the
solution is really trivial. If there are less than 2 elements, there is no
solution.
If all the numbers are non-negative, the problem is completely different from
if you have both signs, all positive is somewhat easier. The smaller sub-array
will contain only 1 element, and the larger subarray will contain either the
front or the back. Start with the front of the array being the 'large' value
and the second item being 'small', we store this as our 'current optimum'. Now
add the 2nd item to 'large' and call the next element 'small'; if this is
better than our first solution, we store it as our current optimum. We go
through the array forwards the whole way through, then we do the same thing
going backwards. The optimal solution we find after both passes is the optimal
solution. This solves in order n (3 passes through n elements). The same logic
works if all the elements are 0 or negative.
If we have both positive and negative numbers, create a 2nd array (partioned
array) 'partitioning' every positive and negative sequence: 2 -1 -2 1 -4 2 8
becomes [2] [-3] [1] [-4] [10]. I am pretty sure this is the right direction,
but from here on out, I bet someone (possibly me with more time) comes up with
something better than I have following.
Now create yet another array combining all the negative elements if and only if
their sum is less than the number between them. Repeat this process until you
cannot. So you get [-6] in this example. Now create yet another array doing
this with the positive values, giving you [2][1][10]. The largest of the
positive and smallest negative are the solution if we can ignore the
requirement the arrays do not overlap, and the solution if they do not overlap.
So far, we've done nothing beyond order n. If they overlap, we can find a
place to split the segment that overlaps fairly easily, and this is almost
always the correct solution, but you can come up with examples where it is not.
I think going back to our partioned array and finding other combinations is the
trick, but cannot think of better than n^2 way to do that.
Of course, you need to store a bit more to go back and find the array indexes,
but that is trivial so I left it out.
I agree this is the best answer on the board, but I think it is still wrong.
- bvbellomo March 09, 2014Consider: -10 7 -3 2 2 -20 1
The best split point considering everything left and right is between -20 and 1, where the best solution is -20 and 7.