我試圖找出一種方法來找出整數中整數的最大總和。xn
在這種情況下，輸入始終是一個整數陣列，任務是使用數字計算最大可能的總和（每個只能使用一次）。54
到目前為止，這是我想出的，但無法弄清楚如何用一種方法完成所有操作。
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.
uj5u.com熱心網友回復：
為了創建遞回實作，首先，您需要對遞回的作業原理有一個深刻的理解。
每個遞回方法都由兩部分組成：
- 基本情況- 表示一個簡單的邊緣情況（遞回終止時的條件），其結果是預先知道的。
- 遞回案例- 進行遞回呼叫和主要邏輯所在的方法部分。
解決此問題的最簡單方法是跟蹤陣列內的位置（如 pos 下面的代碼所示）并在每次方法呼叫時遞增它。
這個問題的基本情況是當 時，即x == 0可以貢獻結果總和的數字的限制已經用盡。因此，回傳值將是0。
遞回情況表示兩種可能的操作：
- 將當前元素添加到sum；
- 忽略它（即丟棄元素）。
第二種情況有一個警告。如果陣列中未訪問的元素數量小于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。
如果您希望以不同方式處理不正確的輸入（例如拋出例外），您可以實作一個單獨的方法來負責驗證輸入。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/454377.html
上一篇：在建構式中使用陣列部署智能合約