The problem is to find the subset of continuous values which adds up to being the highest value. The example here is
So the values 4, -1, 2, 1 add up to be the highest value which is 6.
If the int array is all positive then just add up the entire array.
If all negative values then return 0.
If it's an empty array return 0
I think I understand an all positive array, an all negative and an empty. I figure I would iterate over and test the values as to whether they are all over 0 , all under 0 or empty but if there is a mix of values I'm a bit stumped as to what the best solution is.
I keep thinking of ways that I maybe able to solve this when there is a combination of both positive and negative numbers but most of them seem complicated and most likely NOT the correct way . Is there any tips someone can give me as to what maybe the best solution?
On paper I can come up with a few ideas but none seem ideal or when I test the idea I see an issue with it.
If you find a potential subset then you'll need to keep track of it. I'd start with a very simple class to hold this information.
Now you can write a brute force method with an outer loop with beginIndex going from left to right, and an inner loop going from beginIndex to right. Make a Subset out of it and see if its sum is greater than the sum of a saved maxSubset. Later you can look to optimize like skipping Subsets that begin or end with a negative number.
I haven't found a way to do it in Java the way it can be done in Kotlin. The closest I've gotten so far is this:
I'll leave the implementation of the Kadane class to your imagination but I did get it to pass the tests on codewars.com. The solution, however, ends up being longer than just a straight up imperative implementation.
The best ideas are the crazy ones. If you have a crazy idea and it works, it's really valuable.—Kent Beck
Piet Souris wrote:Don't try this with brute force. There are N^2 (or so) subsets, so that would take a long time, even though you can apply many shortcuts.
I think that's a bit premature here. The most naive brute force solution I can think of actually passes all the tests from Codewars - even though it's O(N^3). It can certainly be improved from there... but it makes a perfectly fine starting point, useful for comparison. Don't let finding the best solution get in the way of finding a solution. Once you have one, you can then find ways to improve on it.
That said, yes there is a much better solution requiring only one loop, no streams, O(N).
LOOK! OVER THERE! (yoink) your tiny ad is now my tiny ad.
Two software engineers solve most of the world's problems in one K&R sized book