algorithm - Int 数组元素的特定最大总和 - C/C++

Question

假设我们有一个数组:7 3 1 1 6 13 8 3 3我必须找到这个数组的最大总和:

• 如果我将 13 加到总和中:我不能从每边添加相邻元素:6 1 和 8 3 不能加到总和中
• 我可以根据需要跳过尽可能多的元素以使总和最大

我的算法是这样的:

• 我取数组的最大元素并将其添加到总和
• 我使该元素和相邻元素为-1
• 我一直这样做，直到再也找不到 max

问题是对于某些特定的测试用例，这个算法是错误的。让我们看看这个:15 40 45 35

根据我的算法:

• 我取 45，让邻居 -1
• 程序结束

正确的做法是 15 + 35 = 50

Answer 1

这个问题可以用dynamic programming解决.

1. 令 A 为数组，令 DP[m] 为 {A[1]~A[m]} 中的最大和>

2. A中的每一个元素只有两种状态，被加入和没有。首先我们假设我们已经确定了DP[1]~DP[m-1]，现在看{A[1]~A[m]}， A[m]只有我们说的两个状态，如果A[m]被加入，A[m-1]和A[m-2]不能加到sum中，所以在add状态下，最大sum为A[m]+DP[m-3](意图: DP[m-3] 是 {A[1]~A[m-3]} 中的最大和，如果 A[m] 没有加入和，最大和是DP[m-1]，所以我们只需要比较A[m]+DP[m-3] 和DP[m-1]，较大的是DP[m]。思路和数学归纳法一样。

3. 所以DP方程是DP[m] = max{ DP[m-3]+A[m], DP[m-1] }，DP[ size(A)]就是结果

复杂度为O(n)，伪代码如下:

 DP[1] = A[1];
 DP[2] = max(DP[1], DP[2]);
 DP[3] = max(DP[1], DP[2], DP[3]);
 for(i = 4; i <= size(A); i++) {
     DP[i] = DP[i-3] + A[i];
     if(DP[i] < DP[i-1])
         DP[i] = DP[i-1];
 }