我必須根據規則找到整數陣列中元素的最大總和：
如果將第二個（或任何連續的）元素添加到總和中 - 僅添加一半的值。為避免這種情況，您可以跳過一個元素。
例如，我們有一個像這樣的輸入 [4, 2, 5, 1, 5] 結果應該是 14。在這種情況下，我們在 0、2 和 4 位置（4 5 5 = 14）取元素，并且跳過位置 1 和 3 的元素
另一個示例的輸入類似于 [3, 1, 10, 6, 3, 10] 在這種情況下，答案應該是 26。我們在位置 0、2、3、5 處取元素，并在位置 1 和 4 處跳過元素。因此 sum 算作：
3 0 10 6/2 0 10 = 26
誰能解釋一下解決這個問題的演算法？或者至少是我應該嘗試解決它的方向。這個任務和動態規劃有什么關系嗎？或者也許有遞回？
提前致謝
uj5u.com熱心網友回復：
一個簡單的最佳解決方案是迭代計算兩個和，都對應于當前索引的最大值i，第一個和 (sum0) 假設當前值 arr[i] 不使用，第二個和 (sum1) 假設當前值 arr [i] 被使用。
sum0_new = max (sum0, sum1);
sum1_new = max (sum0 x, sum1 x/2);
復雜： O(N)
代碼：
這是一個簡單的 C 代碼來說明該演算法。
此實作假定整數除法標準為 2。如果不是這種情況，則易于修改。
輸出：14 26
#include <iostream>
#include <vector>
#include <algorithm>
int max_sum (const std::vector<int>& arr) {
int sum0 = 0;
int sum1 = 0;
for (int x: arr) {
int temp = sum0;
sum0 = std::max (sum0, sum1);
sum1 = std::max (temp x, sum1 x/2);
}
return std::max (sum0, sum1);
}
int main() {
std::vector<std::vector<int>> examples = {
{4, 2, 5, 1, 5},
{3, 1, 10, 6, 3, 10}
};
for (std::vector<int>& arr: examples) {
int sum = max_sum (arr);
std::cout << sum << '\n';
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/409397.html
標籤：