有一个整数数组{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}从3 <4我们打印{5,3}。（包含第一个最小元素的数组）。您可以保留一个数组来跟踪用于{4,4}的{3,5}。
我已经使用父数组修改了代码以跟踪它。另外，我更改了一些变量名称（根据我的理解）。
{3,5}我相信代码可以清理很多，但这是以后的练习:)
输出：
index of elements
add to the current element
更新。添加了一些代码说明
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 5th迭代开始期间，lastSum保持可以添加到currSumth元素的最大值;所以基本上可以通过迭代到ith元素获得的最大值。 lastSum拥有通过迭代到ith元素可以获得的最大值。
在循环结束时，i-2被添加到currSumth元素中并被指定为i-1。如果lastSum小于0，那么ith元素本身被指定为currSum。 lastSum的旧值现在称为i
qazxsw poi＆qazxsw poi持有各自总和值的最新指数。
在下面针对每次迭代显示的所有状态中，最右边的和表示迭代开始时的currSum。 currSum左边的值代表lastSum。他们的指数位置分别记录在lastPos和currPos。
currSum持有使用的currSum最后一个指数的值。该数组稍后用于构造形成最大非相邻和的实际元素集。
lastSumcurrPoslastPospar[]lastSuminitially
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
通过使用par []并循环直到par [p]！= -1，我们可以得到实际形成实际所需元素集的元素索引。直接查看代码。
EG
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
我更喜欢Master Chief的解决方案，但这是另一种方法：
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