I am not sure how to add all the possibilities of elements in an array and find the greatest sum. A little pointer would be of help. I want to do this recursively. I don't need any code. Just ideas as to how I would do it. Thank you very much
Recursive function to test all combinations?
Page 1 of 15 Replies  389 Views  Last Post: 17 May 2014  09:26 PM
Replies To: Recursive function to test all combinations?
#2
Re: Recursive function to test all combinations?
Posted 17 May 2014  07:49 PM
There are many ways to do it. I'm not sure of much you understand combinatorics. Reading about that may help.
In programming you either solve a problem with algorithms or equations. Algorithms sometimes are easier to figure out, but take longer to compute. While equation may be hard to figure what equation to use, but execute really fast.
For this, could you figure how many sums would be created? And if numbers repeat sums would also repeat.
like 1 1 2
sum of 2 would give:
1+1 = 2
1+2 = 3
1+2 = 3
3 sums but only 2 unique sums
In programming you either solve a problem with algorithms or equations. Algorithms sometimes are easier to figure out, but take longer to compute. While equation may be hard to figure what equation to use, but execute really fast.
For this, could you figure how many sums would be created? And if numbers repeat sums would also repeat.
like 1 1 2
sum of 2 would give:
1+1 = 2
1+2 = 3
1+2 = 3
3 sums but only 2 unique sums
#3
Re: Recursive function to test all combinations?
Posted 17 May 2014  08:01 PM
Start by thinking of a dumb answer that ought to work  don't worry about whether it's the best answer or not, just come up with something that you think does the job.
When you've done that, you're in a position to think about how to do it better, but you should always start with something that solves the problem, at least in a small instance.
When you've done that, you're in a position to think about how to do it better, but you should always start with something that solves the problem, at least in a small instance.
#4
Re: Recursive function to test all combinations?
Posted 17 May 2014  09:12 PM
Clearly you want to ignore negative numbers. You can ignore elements valued at 0 as well. So you're only interested in strictly positive elements of the array. Sort the array, start from the end, then run a sum until you hit a nonpositive number.
#5
Re: Recursive function to test all combinations?
Posted 17 May 2014  09:23 PM
Hm. I was assuming that you wanted the sequence producing the greatest possible sum. That is, the indices i,j such that maximize sum(arr[\i], arr[i+1], ... arr[j]). If that's the case, then clearly it's not quite as simple as mac's making it out to be.
Example:
[1, 9, 0, 0, 1, 9]
Clearly the sequence producing the greatest sum is just the whole thing, notwithstanding the zero and negative elements.
However, it's almost as simple. See if you can work out the slight modification to mac's idea that does the job.
EDIT: bloody formatting tags. please disregard the gratuitous backslash
Example:
[1, 9, 0, 0, 1, 9]
Clearly the sequence producing the greatest sum is just the whole thing, notwithstanding the zero and negative elements.
However, it's almost as simple. See if you can work out the slight modification to mac's idea that does the job.
EDIT: bloody formatting tags. please disregard the gratuitous backslash
This post has been edited by jon.kiparsky: 17 May 2014  09:25 PM
#6
Re: Recursive function to test all combinations?
Posted 17 May 2014  09:26 PM
Why would you ignore 0 or negative numbers? And that shouldn't be implementing in a general algorithm. You can add negative numbers. What if they are all negative??
Page 1 of 1
