java - 要打印的数组的非相邻元素的最大总和

Question

有一个整数数组{1,2,3,-1,-3,2,5}，我的工作是打印导致子数组最大和的元素，得到的和是通过添加数组中非相邻元素。

我使用动态规划编写了给出最大总和的代码。但无法打印元素。

public static int maxSum(int arr[]) 
{       
    int excl = 0;
    int incl = arr[0];
    for (int i = 1; i < arr.length; i++) 
    {
        int temp = incl;
        incl = Math.max(Math.max(excl + arr[i], arr[i]), incl);
        excl = temp;
    }
    return incl;
}

例子:

• {1,2,3,-1,-3,2,5} 应该返回 {1,3,5} 因为最大总和是 9
• {4,5,4,3} 在排序时有两个和 {4,4} 和 {5,3}我们得到 {4,4} 和 {3,5} 的两个数组，因为 3<4 我们打印 {3,5}。(包含第一个最小元素的数组)。

Answer 1

您可以保留一个数组来跟踪用于添加到当前元素的元素索引。

我已经用父数组修改了您的代码以跟踪它。另外，我更改了一些变量名称(根据我的理解)。

public static void maxSum(int[] arr){
    int n = arr.length;

    int[] parent = new int[n];
    parent[0] = -1;

    int lastSum = 0; // last sum encountered
    int lastPos = -1; // position of that last sum
    int currSum = arr[0]; // current sum
    int currPos = 0; // position of the current sum

    for (int i = 1; i < n; i++) {
        parent[i] = lastPos;  // save the last sum's position for this element

        // below this it is mostly similar to what you have done;
        // just keeping track of position too.
        int probableSum = Integer.max(arr[i] + lastSum, arr[i]);
        int tSum = currSum;
        int tPos = currPos;
        if(probableSum > currSum){
            currSum = probableSum;
            currPos = i;
        }
        lastSum = tSum;
        lastPos = tPos;
    }
    System.out.println(currSum); // print sum
    System.out.println(Arrays.toString(parent)); // print parent array; for debugging purposes.
    // logic to print the elements
    int p = parent[n - 1];
    System.out.print(arr[n - 1] + " ");
    while (p != -1) {
        System.out.print(arr[p] + " ");
        p = parent[p];
    }
}

我相信代码可以清理很多，但这是以后的练习:)

输出:

{1,2,3,-1,-3,2,5} => 5 3 1

{4,5,4,3} => 3 5

更新。添加了一些代码解释

lastSum 和 currSum 的值在循环执行期间发生变化。最好通过观察它们的值在循环内如何变化来理解它们。

在循环的第 i 次迭代开始期间，lastSum 保存可以添加到第 i 个元素的最大值；所以基本上可以通过迭代到 i-2th 元素获得最大值。 currSum 保存通过迭代到第 i-1 个元素可以获得的最大值。

在循环结束时，lastSum 被添加到第 i 元素并指定为 currSum。如果 lastSum 小于 0，则 i 元素本身被指定为 currSum。 currSum 的旧值现在称为 lastSum

lastPos 和 currPos 保存它们各自总和值的最新索引。

在下面显示的每次迭代的所有状态中，最右边的总和表示迭代开始时的 currSum。 currSum 左边的值表示 lastSum。它们的索引位置分别记录在currPos和lastPos中。

par[] 保存使用的 lastSum 的最后一个索引值。该数组稍后用于构造实际元素集，该元素集形成最大的非相邻总和。

initially

idx = -1,  0,  1, 2,  3,  4, 5, 6
arr =  0,  1,  2, 3, -1, -3, 2, 5
sum =  0   1
par =     -1

---

i=1 iteration state
idx = -1,  0,  1, 2,  3,  4, 5, 6
arr =  0,  1,  2, 3, -1, -3, 2, 5
sum =  0   1,  ?
par =     -1,  !

// before update
currSum = 1, currPos = 0
lastSum = 0, lastPos = -1

// updating
par[1] = lastPos = -1
probableSum = max(2 + 0, 2)  = 2 // max(arr[i] + lastSum, arr[i])
? = max(1, 2) = 2 // max(currSum, probableSum)
! = i = 1

// after update
lastSum = currSum = 1
lastPos = currPos = 0
currSum = ? = 2
currPos = ! = 1

---

i=2 iteration state
idx = -1,  0,  1, 2,  3,  4, 5, 6
arr =  0,  1,  2, 3, -1, -3, 2, 5
sum =  0   1,  2  ?
par =     -1, -1  !

// before update
currSum = 2, currPos = 1
lastSum = 1, lastPos = 0

// updating
par[2] = lastPos = 0
probableSum = max(3 + 1, 3) = 4 // max(arr[i] + lastSum, arr[i])
? = max(2, 4) = 4 // max(currSum, probableSum)
! = i = 2

// after update
lastSum = currSum = 2
lastPos = currPos = 1
currSum = ? = 4
currPos = ! = 2

---

i = 3 iteration state
idx = -1,  0,  1, 2,  3,  4, 5, 6
arr =  0,  1,  2, 3, -1, -3, 2, 5
sum =  0   1,  2  4   ?
par =     -1, -1  0   !

// before update
currSum = 4, currPos = 2
lastSum = 2, lastPos = 1

//updating
par[3] = lastpos = 1
probableSum = max(-1 + 2, -1) = 1 // max(arr[i] + lastSum, arr[i])
? = max(4, 1) = 4 // max(currSum, probableSum) ; no update in ?'s value
! = currPos = 2 // as ?'s value didn't update

// after update
lastSum = currSum = 4
lastPos = currPos = 2
currSum = ? = 4
currPos = ! = 2

---

i = 4 iteration
idx = -1,  0,  1, 2,  3,  4, 5, 6
arr =  0,  1,  2, 3, -1, -3, 2, 5
sum =  0   1,  2  4   4   ?
par =     -1, -1  0   1   !

// before update
currSum = 4, currPos = 2
lastSum = 4, lastPos = 2

// updating
par[4] = lastPos = 2
probableSum = max(-3 + 4, -3) = 1 // max(arr[i] + lastSum, arr[i])
? = max(4, 1) = 4 // max(currSum, probableSum) ; no update in ?'s value
! = currPos = 2 // as ?'s value didn't update

// after update
lastSum = currSum = 4
lastPos = currPos = 2
currPos = ? = 4
currPos = ! = 2

---

i = 5 iteration
idx = -1,  0,  1, 2,  3,  4, 5, 6
arr =  0,  1,  2, 3, -1, -3, 2, 5
sum =  0   1,  2  4   4   4  ?
par =     -1, -1  0   1   2  !

// before update
currSum = 4, currPos = 2
lastSum = 4, lastPos = 2

// updating
par[5] = lastPos = 2
probableSum = max(2 + 4, 2) = 6 // max(arr[i] + lastSum, arr[i])
? = max(4, 6) = 6 // max(currSum, probableSum)
! = i = 5

// after update
lastSum = currSum = 4
lastPos = currPos = 2
currPos = ? = 6
currPos = ! = 5

---

i = 6 iteration state
idx = -1,  0,  1, 2,  3,  4, 5, 6
arr =  0,  1,  2, 3, -1, -3, 2, 5
sum =  0   1,  2  4   4   4  6  ?
par =     -1, -1  0   1   2  2  !

// before update
currSum = 6, currPos = 5
lastSum = 4, lastPos = 2

// updating
par[6] = lastPos = 2
probableSum = max(5 + 4, 5) = 9 // max(arr[i] + lastSum, arr[i])
? = max(6, 9) = 9 // max(currSum, probableSum)
! = i = 6

// after update
lastSum = currSum = 6
lastPos = currPos = 5
currPos = ? = 9
currPos = ! = 6

---

after all iteration state
idx = -1,  0,  1, 2,  3,  4, 5, 6
arr =  0,  1,  2, 3, -1, -3, 2, 5
sum =  0   1,  2  4   4   4  6  9
par =     -1, -1  0   1   2  2  2

通过使用 par[] 并循环直到 par[p] != -1 我们可以获得实际形成实际所需元素集的元素索引。直接查看代码。

例如

p = last = 6
arr[p] = arr[6] = 5 // element

p = par[p] = par[6] = 2
arr[p] = arr[2] = 3 // element

p = par[p] = par[2] = 0
arr[p] = arr[0] = 1 // element

p = par[p] = par[0] = -1 // stop