Win a copy of Transfer Learning for Natural Language Processing (MEAP) this week in the Artificial Intelligence and Machine Learning forum!
  • 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
  • Tim Cooke
  • Paul Clapham
  • Devaka Cooray
  • Bear Bibeault
Sheriffs:
  • Junilu Lacar
  • Knute Snortum
  • Liutauras Vilda
Saloon Keepers:
  • Ron McLeod
  • Stephan van Hulst
  • Tim Moores
  • Tim Holloway
  • Piet Souris
Bartenders:
  • salvin francis
  • Carey Brown
  • Frits Walraven

How would you work this problem?

 
Ranch Hand
Posts: 323
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: 7065
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.
 
Sheriff
Posts: 15519
263
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
Sheriff
Posts: 15519
263
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: 323
6
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks guys.  I'll give it a go from this.
 
Saloon Keeper
Posts: 3893
154
  • 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: 7065
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
Sheriff
Posts: 15519
263
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
Sheriff
Posts: 15519
263
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
Sheriff
Posts: 15519
263
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
Saloon Keeper
Posts: 3893
154
  • 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
Sheriff
Posts: 15519
263
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: 3503
37
  • 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).
 
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
https://coderanch.com/wiki/718759/books/Building-World-Backyard-Paul-Wheaton
    Bookmark Topic Watch Topic
  • New Topic