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);

任何人都可以帮助澄清这个解决方案吗？

标签： algorithm

Answer 1

这是一个动态编程/递归解决方案，它基本上着眼于每个位置的 2 个场景，是否包含或排除一个值。由于数组中的所有值都是正数，因此该解决方案有效。如果数组包含负值，此解决方案将不起作用。

arr = Array of numbers
af = function(currentIndex, cummulativeSum){
 if (currentIndex >= arr.length) return cummulativeSum

return Math.max(af(currentIndex+2,cummulativeSum+arr[currentIndex]), af(currentIndex+1, cummulativeSum))
}