programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
• Campbell Ritchie
• Paul Clapham
• Ron McLeod
• paul wheaton
• Devaka Cooray
Sheriffs:
• Jeanne Boyarsky
• Tim Cooke
• Liutauras Vilda
Saloon Keepers:
• Tim Moores
• Tim Holloway
• Stephan van Hulst
• Carey Brown
• Piet Souris
Bartenders:
• salvin francis
• Mikalai Zaikin
• Himai Minh

# How would you work this problem?

Ranch Hand
Posts: 327
6
• Number of slices to send:
Optional 'thank-you' note:
I'm on another codewar problem here https://www.codewars.com/kata/54521e9ec8e60bc4de000d6c/train/java

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.

Saloon Keeper
Posts: 8102
71
• 2
• Number of slices to send:
Optional 'thank-you' note:
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.

Sheriff
Posts: 16146
269
• 1
• Number of slices to send:
Optional 'thank-you' note:
For the sake of simplicity, I would say the rule is that if the total of a sequence or subsequence is less than 0, then you should consider it as 0.

Junilu Lacar
Sheriff
Posts: 16146
269
• 1
• Number of slices to send:
Optional 'thank-you' note:
I would also look into something like findFirst() or findAny() to see if there are negative numbers in a sequence/subsequence. Then use the IntStream.sum() function.

Lisa Austin
Ranch Hand
Posts: 327
6
• Number of slices to send:
Optional 'thank-you' note:
Thanks guys.  I'll give it a go from this.

Saloon Keeper
Posts: 4387
163
• 2
• Number of slices to send:
Optional 'thank-you' note:
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.

Look for "largest sum of subarrays" on the internet, where you find Kadane's O(N) solution. Beware though: many of these pages contain ready-to--run code.

Carey Brown
Saloon Keeper
Posts: 8102
71
• Number of slices to send:
Optional 'thank-you' note:

Junilu Lacar wrote:I would also look into something like findFirst() or findAny() to see if there are negative numbers in a sequence/subsequence. Then use the IntStream.sum() function.

I'm not sure where your headed with this. Even the max subsequence can have negative numbers in it and negative numbers still need to be added into the sum.

Junilu Lacar
Sheriff
Posts: 16146
269
• 1
• Number of slices to send:
Optional 'thank-you' note:

Carey Brown wrote:I'm not sure where your headed with this. Even the max subsequence can have negative numbers in it and negative numbers still need to be added into the sum.

I'm thinking of recursive calls and if there are no negatives, you can stop the recursion at that point.

Junilu Lacar
Sheriff
Posts: 16146
269
• Number of slices to send:
Optional 'thank-you' note:

Piet Souris wrote:Look for "largest sum of subarrays" on the internet, where you find Kadane's O(N) solution.

Thanks for the tip. Interesting problem.

Here's what I came up with in Kotlin:

I have to admit that's going to look very cryptic to the uninitiated and even if you know about fold, let, also in Kotlin it might take a few seconds to decipher it.

Junilu Lacar
Sheriff
Posts: 16146
269
• Number of slices to send:
Optional 'thank-you' note:
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.

Piet Souris
Saloon Keeper
Posts: 4387
163
• Number of slices to send:
Optional 'thank-you' note:
I would use a similar construction in Java, like this (it uses the not so much used three parameter version of Stream.collect)

for a suitable Kadane class. But shorter and easier to understand is a simple for loop.

Junilu Lacar
Sheriff
Posts: 16146
269
• Number of slices to send:
Optional 'thank-you' note:
Yeah, I was looking at collect() as well. I agree, a straightforward for-loop seems better for this problem.

Rancher
Posts: 3851
50
• 3
• Number of slices to send:
Optional 'thank-you' note:

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).