CODEWITHSUNDEEP
javaarraysrecursion
Morgan Henry
Morgan Henry

Reputation: 5

Java Recursion to find MAX sum in array

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?

Upvotes: 0

Views: 1361

Answers (1)

starikoff
starikoff

Reputation: 1650

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.

Upvotes: 1

Related Questions