Java Recursion to find MAX sum in array

Question

I am trying to figure out a solution to calculate the highest sum of numbers in an array. However, my limitation is that I cannot use adjacent values in the array.

If I am given the array int [] blocks = new int[] {15, 3, 6, 17, 2, 1, 20}; the highest sum calculated is 52 (15+17+20). My goal is to go from a recursive solution to a solution that uses dynamic programming, however, I am having trouble with the recursive solution.

The base cases that I have initialized:

if(array.length == 0)
    return 0;
if(array.length == 1)
    return array[0];

After creating the base cases, I am unsure of how to continue the recursive process. I initially tried to say that if the array was of certain length, then I can calculate the max(Math.max) of the calculations: e.g. if array.length = 3 return Math.max(array[0], array[1], array[2], array[0]+ array[2])

The problem I then run into is that I could be given an array of length 100. How can I use recursion in this problem?

Why are you keen on adding only three numbers in your example 15+17+20 , is the output restricted up to three numbers? — SomeDude
– SomeDude, Commented Apr 23, 2017 at 14:15
Those are the numbers that get me the highest sum. I can easily do 15 + 6 + 2 + 20 but that only gives me 43. — Morgan Henry
– Morgan Henry, Commented Apr 23, 2017 at 14:19
well, doing 15+3+6+17+2+1+20 gives me 64. That beats you by 12. — Abacus
– Abacus, Commented Apr 23, 2017 at 19:06
Yes, I definitely agree, only problem is P.J., I cannot use adjacent spots in the array, meaning I can't use all of the values, furthermore if Im using 15 I can't use 3. Catch my drift? — Morgan Henry
– Morgan Henry, Commented Apr 26, 2017 at 20:12

starikoff · Accepted Answer · 2017-04-26 20:48:09Z

1

I think recursive solution to your problem is (in pseudocode):

maxsum(A,0) = 0
maxsum(A,1) = A[0]
maxsum(A,k) = max(maxsum(A,k-2)+A[k-1], maxsum(A,k-1)), for k >= 2

Where maxsum(A,k) means the maximal sum for a subarray of array A starting from 0 and having length k. I'm sure you'll easily translate that into Java, it translates almost literally.

answered Apr 26, 2017 at 20:48

starikoff

1,67019 silver badges25 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Java Recursion to find MAX sum in array

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related