algorithm - 非相邻值的最大总和

Question

我在论坛上找到了几个解决这个问题的方法，但似乎没有一个对我有帮助。主要是因为我找到了一种解决方案，但不知道它的工作原理和原因。

问题陈述:对于给定的正整数数组，找出不相邻元素的最大总和。

问题还严格规定解必须在线性时间内。这是我发现的:

int max1 = 0 
int max2 = a[0];

int i;
for(i = 1; i<n; i++){
    int new_max1 = max(max2, max1);
    max2 = max1 + a[i];
    max1 = new_max1;
}
return max(max1, max2);

谁能帮助阐明这个解决方案？

Answer 1

想想这些问题:

P1i:找到包含第 i 个的 Array[0:i+1] 的非相邻元素的最大总和。
P2i:找到 Array[0:i+1] 中不包含第 i 个的非相邻元素的最大总和。

其中 Array[i,j] 是 Array 的子集，从第 i 个到第 (j-1) 个。

想想如何根据 {P1i, P2i} 解决 {P1(i+1), P2(i+1)}。

大功告成!

更明确地说:

基本情况 (i=0) 是 {Array[0], i}

那么对于 i=1，P11, P21 的解决方案是 {(Array[1] + P10), P20}

那么对于 i=2，P12, P22 的解是 {(Array[2] + P21), P11}

那么对于 i=3，P13, P23 的解决方案是 {(Array[3] + P22), P12}

那么对于 i=4，P14, P24 的解是 {(Array[3] + P23), P13}

...

您正在寻找的解决方案是 max(P1(n-1), P2(n-1))。

您发布的代码是迭代的。它可以很容易地以递归形式重写。玩得开心!