要打印的数组中非相邻元素的最大和 [英] Maximum sum of non adjacent elements of an array, to be printed
问题描述
有一个整数数组{1,2,3，-1，-3,2,5}，我的工作是打印导致子数组最大和的元素，得到的和是通过加
There is an array of integers {1,2,3,-1,-3,2,5}, my job is to print the elements which leads to max sum of the sub array, the sum obtained is by adding non adjacent elements in the array.
我使用动态编程编写了给出最大和的代码。
I written the code to give the max sum, using dynamic programming. but not able to print the elements.
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}。（包含第一个最小元素的数组）。
{1,2,3,-1,-3,2,5}should return{1,3,5}as max sum is 9{4,5,4,3}has two sums{4,4}and{5,3}, on sorting the two arrays we get{4,4}and{3,5}since 3<4 we print{3,5}.(the array containing the first smallest element).
推荐答案
您可以保留一个数组来跟踪元素的索引，该索引用于添加到当前元素。
You can keep an array to keep track of the index of elements which is used to add to the current element.
我已经使用父数组修改了您的代码以跟踪该代码。另外，根据我的理解，我也更改了一些变量名。
I have modified your code with a parent array to keep track of that. Also, I have changed some variable names (as per my understanding).
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 在循环执行期间发生更改。通过观察其值在循环内如何变化，可以最好地理解它们。
The value of lastSum & currSum changes within the execution of the loop. They are best understood by observing how their value changes inside the loop.
在循环的 i 次开始时 lastSum 拥有可以添加到第 i 个元素的最大值；因此基本上可以通过迭代最多 i-2 个元素而获得的最大值。
currSum 拥有通过迭代最多 i-1 个元素可获得的最大值。
During the start of the ith iteration of the loop lastSum holds the largest value that can be added to the ith element; so basically largest value that can be obtained by iterating upto i-2th element.
currSum holds the largest value that can be obtained by iterating upto i-1th element.
在循环结束时，将 lastSum 添加到 i 个元素，并指定为 currSum 。如果 lastSum 小于0，则将 i th个元素本身指定为 currSum 。现在旧值 currSum 现在称为 lastSum
At the end of the loop lastSum is added to the ith element and is designated as currSum. If lastSum is smaller than 0, then ith element itself is designated as currSum. And old value of currSum is now called lastSum
lastPos & currPos 保存相应总和值的最新索引。
lastPos & currPos holds latest index of thier respective sum values.
在以下所示的所有状态下，每次迭代的最右边sum在迭代开始时表示 currSum 。 currSum 左侧的值表示 lastSum 。它们的索引位置记录在 currPos &中。分别是 lastPos 。
In all the states shown below for each iteration, the rightmost sum represents currSum at the start of the iteration. Value to the left of currSum represents lastSum. Their index position is recorded in currPos & lastPos respectively.
par [] 保留值最后使用的 lastSum 的索引。后来，该数组用于构造实际元素集，从而形成最大的非相邻和。
par[] holds the value of the last index of lastSum used. This array is later used to construct the actual set of elements which forms largest non-adjacent sum.
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，我们可以获得元素的索引，这些元素实际上形成了实际所需元素的集合。
By using the par[] and looping until par[p] != -1 we can get the index of elements which actually forms set of actual required elements. Check out the code its straight forward.
例如
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
这篇关于要打印的数组中非相邻元素的最大和的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
