Max Sum of X integers out of N numbers using recursion-CodePudding

I am trying to figure out a way to find out the max sum of x number of integers out of n number of integers.

In this case, the input is always an array of 5 integers and the task is to calculate the max possible sum using 4 numbers (each can be used only once).

Here is what I've come up with so far, but can't figure out how to do it all in a single method.

public static int maxSum(int[] numbers, int i) {
    return sum(numbers, i) - min(numbers, i);
}

public static int sum(int[] numbers, int i) {
    if (i == 1) return numbers[0];
    return numbers[i - 1]   sum(numbers, i - 1);
}

public static int min(int[] numbers, int i) {
    if (i == 1) return numbers[0];
    return Math.min(numbers[i - 1], min(numbers, i - 1));
}

With this input: int[] arr = {1, 2, 3, 4, 5}; the program should print out of 14.

CodePudding user response：

In order to create a recursive implementation, first, you need to have a firm understanding on how recursion works.

Every recursive method consists of two parts:

Base case - that represents a simple edge-case (condition when recursion terminates) for which the outcome is known in advance.
Recursive case - the part of the method where recursive calls are made and where the main logic resides.

The simplest way to approach this problem is to track the position (denoted as pos in the code below) inside the array and increment it at each method call.

The base case for this problem, is a situation when x == 0, i.e. the limit of numbers that can contribute the resulting sum was exhausted. Therefore, the return value will be 0.

The recursive case represents the two possible actions:

add the current element to the sum;
ignore it (i.e. discard the element).

There's a caveat with the second case. We can't discard the current element if the number of not-visited elements in the array less than the current value of x (the number of elements to add). That will spawn unnecessary recursive branches and might lead to incorrect results when the given array contains negative numbers.

For that reason, the second branch of execution is enclosed by the if statement that check whether the remaining number of elements is enough.

In both scenarios, when the method is being called recursively, position needs to be incremented by 1.

And when the method is being invoked from the client code (the first method call) we need to pass 0 as a starting position.

public static int getMaxSum(int[] arr, int pos, int elements) {
    if (elements == 0) { // base case
        return 0;
    }
    // The two possible actions: add or ignore the current element
    int take = arr[pos]   getMaxSum(arr, pos   1, elements - 1); // it's always possible to take this option when `elements > 0` 

    if (arr.length - pos > elements) { // this option is available only if the number of not-encountered elements is greater or equals to the number of `elements` that have to be added to the sum
        int discard = getMaxSum(arr, pos   1, elements);
        return Math.max(take, discard);
    }
    return take;
}

main() - demo

public static void main(String[] args) {
    System.out.println(getMaxSum(new int[]{1, 2, 3, 4, 5}, 0, 4));
    System.out.println(getMaxSum(new int[]{8, 1, -3, 5, -9}, 0, 4));
}

Output

14
11

Note that in the case if provided number of elements that have to constitute the sum will be negative or greater than the length of the given array, the method will return 0.

You might implement a separate method that will be responsible for validating the input, if you want the incorrect input to be handled differently (for instance throw an exception).