使用递归从 N 个数字中提取 X 个整数的最大总和

Question

我正在尝试找出一种方法，从 n 个整数中找出 x 个整数的 最大总和 。

在这种情况下，输入总是 array 5 个整数，任务是计算 最大可能总和 使用 4 个数字（每个数字只能使用一次）。

这是我到目前为止的想法，但无法弄清楚如何用一种方法完成所有工作。

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));
}

使用此输入：int[] arr = {1, 2, 3, 4, 5}; 程序应打印出 14。

Answer 1

为了创建递归实现，首先，您需要对递归的工作原理有一个深刻的理解。

每个递归方法都由两部分组成：

基本情况 - 表示一个简单的edge-case（递归终止时的条件），其结果是预先知道的。
递归案例 - 方法中进行递归调用和主要逻辑所在的部分。

解决此问题的最简单方法是跟踪位置（表示为 pos 在下面的代码中) 在数组中并且 在每次方法调用时递增 它。

此问题的 基本情况 是 x == 0 的情况，即可以贡献结果总和的数字限制已经用尽。因此，return 值 将是 0。

递归情况表示两种可能的操作：

将当前元素加到总和;
忽略它（即丢弃该元素）。

第二种情况有一个警告。如果数组中not-visited个元素的个数小于x的当前值，我们不能丢弃当前元素（个数要添加的元素数量)。这将产生不必要的递归分支，并可能在给定数组包含负数时导致不正确的结果。

因此，第二个执行分支包含在 if 语句中，检查剩余元素数是否足够。

在这两种情况下，递归调用方法时，position需要增加1。

并且当从客户端代码调用方法时（第一个方法调用）我们需要传递0作为起始位置。

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() - 演示

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));
}

输出

14
11

注意如果提供的元素数量必须构成 sum 将为负数或大于长度给定数组，该方法将return 0.

如果您希望以不同方式处理不正确的输入（例如抛出异常），您可以实现一个单独的方法来负责验证输入。

使用递归从 N 个数字中提取 X 个整数的最大总和

Max Sum of X integers out of N numbers using recursion

java

arrays

algorithm

recursion