有一個(gè)整數(shù)數(shù)組{1,2,3,-1,-3,2,5}，我的工作是打印導(dǎo)致子數(shù)組最大和的元素，得到的和是通過添加不相鄰的元素在數(shù)組中。我使用動(dòng)態(tài)編程編寫了代碼以給出最大總和。但無法打印元素。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}應(yīng)該返回{1,3,5}最大總和為9{4,5,4,3} 有兩個(gè) {4,4}和{5,3}，在對(duì)我們得到的兩個(gè)數(shù)組進(jìn)行排序時(shí){4,4}，{3,5}由于 3<4 我們打印{3,5}.（包含第一個(gè)最小元素的數(shù)組）。
2 回答
交互式愛情
TA貢獻(xiàn)1712條經(jīng)驗(yàn) 獲得超3個(gè)贊
您可以保留一個(gè)數(shù)組來跟蹤index of elements用于add to the current element.
我已經(jīng)使用父數(shù)組修改了您的代碼以跟蹤它。另外，我更改了一些變量名稱（根據(jù)我的理解）。
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];
}
}
我相信代碼可以清理很多，但這是以后的練習(xí):)
輸出：
{1,2,3,-1,-3,2,5} => 5 3 1
{4,5,4,3} => 3 5
更新。添加了一些代碼解釋
lastSum&的值currSum在循環(huán)執(zhí)行期間發(fā)生變化。最好通過觀察它們的值在循環(huán)內(nèi)如何變化來理解它們。
i在循環(huán)的第 th 次迭代開始期間，lastSum保存可以添加到第ith 個(gè)元素的最大值；i-2所以基本上可以通過迭代到第一個(gè)元素 來獲得最大值。保存通過迭代到第 th 個(gè)元素currSum可以獲得的最大值。i-1
在循環(huán)結(jié)束時(shí)lastSum添加到第ith 個(gè)元素并指定為currSum。如果lastSum小于 0，則將i元素本身指定為currSum。舊值currSum現(xiàn)在稱為lastSum
lastPos&currPos保存各自總和值的最新索引。
在下面顯示的每次迭代的所有狀態(tài)中，最右邊的和表示currSum迭代開始時(shí)。左側(cè)的值currSum表示lastSum。它們的索引位置分別記錄在currPos&lastPos中。
par[]保存使用的最后一個(gè)索引的值lastSum。該數(shù)組稍后用于構(gòu)造形成最大非相鄰和的實(shí)際元素集。
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[] 并循環(huán)直到 par[p] != -1 我們可以獲得元素的索引，它實(shí)際上形成了一組實(shí)際需要的元素。直接查看代碼。
例如
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
收到一只叮咚
TA貢獻(xiàn)1821條經(jīng)驗(yàn) 獲得超5個(gè)贊
我更喜歡士官長的解決方案，但這是另一種方法：
/** returns a list of indices which contain the elements that make up the max sum */
public static List<Integer> maxSum(int arr[]) {
int priorMaxSum = 0;
List<Integer> priorMaxSumList = new ArrayList<>();
// initial max sum
int maxSum = arr[0];
List<Integer> maxSumList = new ArrayList<>();
maxSumList.add(0);
for (int i = 1; i < arr.length; i++) {
final int currSum;
final List<Integer> currSumList;
if (priorMaxSum > 0) {
// if the prior sum was positive, then continue from it
currSum = priorMaxSum + arr[i];
currSumList = new ArrayList<>(priorMaxSumList);
} else {
// if the prior sum was not positive, then throw it out and start new
currSum = arr[i];
currSumList = new ArrayList<>();
}
currSumList.add(i);
// update prior max sum and list
priorMaxSum = maxSum;
priorMaxSumList = new ArrayList<>(maxSumList);
if (currSum > maxSum) {
// update max sum
maxSum = currSum;
maxSumList = currSumList;
}
}
return maxSumList;
}
public static void main(String[] args) throws Exception {
int[] a = {1, 2, 3, -5, -3, 2, 5};
List<Integer> l = maxSum(a);
System.out.println(
"indices {" + l.stream().map(String::valueOf).collect(Collectors.joining(", ")) + "}");
System.out.println("values {"
+ l.stream().map(i -> String.valueOf(a[i])).collect(Collectors.joining(", ")) + "}");
}
添加回答
舉報(bào)
0/150
提交
取消