查找数组中元素的最大总和(带扭曲)

Question

给定具有+ ve和-ve整数的数组,找到最大总和,以便不允许跳过2个连续元素(即,您必须选择其中至少一个向前移动).

例如: -

10,20,30,-10,-50,40,-50,-1,-3

输出:10 + 20 + 30-10 + 40-1 = 89

Answer 1

使用动态编程方法可以解决此问题.

让arr成为给定的数组,并选择存储最佳解决方案的数组. opt [i]是从元素i开始可以获得的最大总和.

opt[i] = arr[i] + (some other elements after i)

现在为了解决这个问题,我们向后迭代数组arr,每次都存储答案opt [i].由于我们不能跳过2个连续元素,因此必须在opt [i]中包含元素i + 1或元素i + 2.

所以每个我, opt[i] = arr[i] + max(opt[i+1], opt[i+2])

请参阅此代码以了解:

int arr[n];  // array of given numbers. array size = n.
nput(arr, n);   // input the array elements (given numbers)

int opt[n+2];   // optimal solutions. 
memset(opt, 0, sizeof(opt));    // Initially set all optimal solutions to 0.

for(int i = n-1; i >= 0; i--) {
    opt[i] = arr[i] + max(opt[i+1], opt[i+2]);
}

ans = max(opt[0], opt[1])   // final answer.

观察到opt数组有n + 2个元素.这是为了避免在我们尝试访问最后一个元素(n-1)的opt [i + 1]和opt [i + 2]时获得非法内存访问异常(内存超出范围).

请参阅上面给出的算法的工作实现

Answer 2

使用重复计算:

dp[i] = max(dp[i - 1] + a[i], <- take two consecutives
            dp[i - 2] + a[i], <- skip a[i - 1])

基础案例作为练习留下.