使用递归的N个数中X个整数的最大和

Question

我想找出一种方法，从n整数中找出x整数的最大和。

在这种情况下，输入总是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

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

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

• 基本情况-表示一个简单的边缘情况（递归终止时的条件），其结果是预先已知的

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

这个问题的基本情况是，当x==0或当位置命中大于给定数组中最后一个有效索引的索引时。也就是说，在这两种情况下，总和都没有数字可加。因此，html" target="_blank">返回值将为0。

递归案例代表两种可能性：

• 将当前元素添加到总和中；
• 忽略它（即丢弃元素）。

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

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

public static int getMaxSum(int[] arr, int pos, int elements) {
    if (elements == 0 || pos == arr.length) { // base case: no elements left to add or index is invalid
        return 0;
    }
    // two possibilities: add or ignore the current element
    int take = arr[pos] + getMaxSum(arr, pos + 1, elements - 1);
    int discard = getMaxSum(arr, pos + 1, elements);

    return Math.max(take, discard);
}

main（）-demo

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

输出

25
14