• Post Reply Bookmark Topic Watch Topic
  • New Topic
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 all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Ron McLeod
  • Paul Clapham
  • Bear Bibeault
  • Junilu Lacar
Sheriffs:
  • Jeanne Boyarsky
  • Tim Cooke
  • Henry Wong
Saloon Keepers:
  • Tim Moores
  • Stephan van Hulst
  • Tim Holloway
  • salvin francis
  • Frits Walraven
Bartenders:
  • Scott Selikoff
  • Piet Souris
  • Carey Brown

How would you work this problem?

 
Ranch Hand
Posts: 325
6
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.











 
Bartender
Posts: 7295
65
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows
  • Likes 2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Marshal
Posts: 15875
265
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Marshal
Posts: 15875
265
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 325
6
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks guys.  I'll give it a go from this.
 
Bartender
Posts: 4066
156
  • Likes 2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Bartender
Posts: 7295
65
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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
Marshal
Posts: 15875
265
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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
Marshal
Posts: 15875
265
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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
Marshal
Posts: 15875
265
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Bartender
Posts: 4066
156
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Marshal
Posts: 15875
265
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Yeah, I was looking at collect() as well. I agree, a straightforward for-loop seems better for this problem.
 
Rancher
Posts: 3625
40
  • Likes 3
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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).
 
He baked a muffin that stole my car! And this tiny ad:
Thread Boost feature
https://coderanch.com/t/674455/Thread-Boost-feature
    Bookmark Topic Watch Topic
  • New Topic