Максимальная сумма X целых чисел из N чисел с использованием рекурсии
Я пытаюсь найти способ узнать максимальная суммаx числа целых чисел из n числа целых чисел.
В этом случае вход всегда представляет собой множество из 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.
Ответы 1
Чтобы создать рекурсивную реализацию, во-первых, вам нужно четко понимать, как работает рекурсия.
Каждый рекурсивный метод состоит из двух частей:
- Базовый вариант — представляет собой простой пограничный случай (условие, когда рекурсия завершается), для которого результат известен заранее.
- Рекурсивный случай — часть метода, где выполняются рекурсивные вызовы и где находится основная логика.
Самый простой способ решить эту проблему — отслеживать позиция (обозначается какposв коде ниже) внутри массива и приращение при каждом вызове метода.
базовый вариант для этой задачи - это ситуация, когда x == 0, т.е. исчерпан лимит чисел, которые могут внести вклад в результирующую сумму. Следовательно, возвращаемое значение будет 0.
рекурсивный случай представляет два возможных действия:
- добавить текущий элемент в сумма;
- игнорировать его (т.е. отбросить элемент).
Есть предостережение со вторым корпусом. Мы не можем отбросить текущий элемент, если количество непосещаемые элементы в массиве меньше текущего значения x (количество добавляемых элементов). Это приведет к появлению ненужных рекурсивных ветвей и может привести к неправильным результатам, когда данный массив содержит отрицательные числа.
По этой причине вторая ветвь выполнения заключена в оператор if, который проверяет, достаточно ли оставшегося количества элементов.
В обоих сценариях, когда метод вызывается рекурсивно, позиция необходимо увеличить на 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
Примечание, что в случае, если предоставленное количество элементов, которые должны составлять сумма, будет отрицательным или больше, чем длина данный массив, метод вернет 0.
Вы можете реализовать отдельный метод, который будет отвечать за проверку ввода, если вы хотите, чтобы неправильный ввод обрабатывался по-другому (например генерировать исключение).
Я должен что-то упустить. Если вы хотите найти наибольшую сумму 4 целых чисел среди 5, не можете ли вы просто отбросить наименьшее число из 5?