arrays - 当没有两个元素相邻时，如何获取用于查找数组元素最大总和的数字/索引

Question

我发现下面提到的这些文章对于在没有两个元素相邻时找到数组元素的最大总和很有用。 Maximum sum of non consecutive elements https://www.geeksforgeeks.org/maximum-sum-such-that-no-two-elements-are-adjacent/

但我无法理解背后的逻辑，如何获取用于查找最大和的数字。例如:

array => {2, 5, 10, 1, 10}

通过使用 2、10 和 10，最大和将是 22，现在如何找到在大型数组的情况下使用的数字/索引。在此示例中，如何找到我使用了数组的第 2、10、10 或第 0、2、4 个索引？非常感谢任何类型的帮助。

Maximum sum of non consecutive elements https://www.geeksforgeeks.org/maximum-sum-such-that-no-two-elements-are-adjacent/

Answer 1

正如您分享的问题中所说:定义数组 M where M[i] = max(M(i - 1), M(i - 2) + A[i ]) 对于 i = 1, ..., n。

此外，创建数组 I，它将包含所选索引。

首先通过选择 M 的前 2 个元素(避免边缘情况)来初始化所有内容:

A = 2, 5, 10, 1, 10 // input array

M = [A[0]]; // index 0 of M is only first element
I = []; // init empty index array
if (A[0] > A[1]) { // if first element bigger
    M[1] = A[0]; //choose him for second place also
    I = [true, false]; // set first two indexs as taking the first element in A and not the second
} else { // the second element is bigger
    M[1] = A[1]; // assign him to M
    I = [false, true] //set I for not taking the first element but the second one
}

现在循环所有的 A 数组:

for i 2 to cnt(A)-1 {
    if (M[i-1] > M[i-2] + A[i]) { // if prefer to take last place
        M[i] = M[i-1]; // set current max at i
        I[i] = false; // we don't take the current places
    } else {
        M[i] = M[i-2] + A[i]; // set current max at i
        I[i] = true; I[i-1] = false, I[i-2] = true; //change older value as decided to take this path
    }
}

例如:

A = 2, 5, 10, 1, 10
M = 2, 5, 12, 12, 22
I = T, F, T, F, T