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

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

您可以保留一个数组来跟踪index of elements用于add to the current element.我已经使用父数组修改了您的代码以跟踪它。另外，我更改了一些变量名称（根据我的理解）。public static void maxSum(int[] arr){&nbsp; &nbsp; int n = arr.length;&nbsp; &nbsp; int[] parent = new int[n];&nbsp; &nbsp; parent[0] = -1;&nbsp; &nbsp; int lastSum = 0; // last sum encountered&nbsp; &nbsp; int lastPos = -1; // position of that last sum&nbsp; &nbsp; int currSum = arr[0]; // current sum&nbsp; &nbsp; int currPos = 0; // position of the current sum&nbsp; &nbsp; for (int i = 1; i < n; i++) {&nbsp; &nbsp; &nbsp; &nbsp; parent[i] = lastPos;&nbsp; // save the last sum's position for this element&nbsp; &nbsp; &nbsp; &nbsp; // below this it is mostly similar to what you have done;&nbsp; &nbsp; &nbsp; &nbsp; // just keeping track of position too.&nbsp; &nbsp; &nbsp; &nbsp; int probableSum = Integer.max(arr[i] + lastSum, arr[i]);&nbsp; &nbsp; &nbsp; &nbsp; int tSum = currSum;&nbsp; &nbsp; &nbsp; &nbsp; int tPos = currPos;&nbsp; &nbsp; &nbsp; &nbsp; if(probableSum > currSum){&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; currSum = probableSum;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; currPos = i;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; lastSum = tSum;&nbsp; &nbsp; &nbsp; &nbsp; lastPos = tPos;&nbsp; &nbsp; }&nbsp; &nbsp; System.out.println(currSum); // print sum&nbsp; &nbsp; System.out.println(Arrays.toString(parent)); // print parent array; for debugging purposes.&nbsp; &nbsp; // logic to print the elements&nbsp; &nbsp; int p = parent[n - 1];&nbsp; &nbsp; System.out.print(arr[n - 1] + " ");&nbsp; &nbsp; while (p != -1) {&nbsp; &nbsp; &nbsp; &nbsp; System.out.print(arr[p] + " ");&nbsp; &nbsp; &nbsp; &nbsp; p = parent[p];&nbsp; &nbsp; }}我相信代码可以清理很多，但这是以后的练习:)输出：{1,2,3,-1,-3,2,5} => 5 3 1{4,5,4,3} => 3 5更新。添加了一些代码解释lastSum&的值currSum在循环执行期间发生变化。最好通过观察它们的值在循环内如何变化来理解它们。i在循环的第 th 次迭代开始期间，lastSum保存可以添加到第ith 个元素的最大值；i-2所以基本上可以通过迭代到第一个元素 来获得最大值。保存通过迭代到第 th 个元素currSum可以获得的最大值。i-1在循环结束时lastSum添加到第ith 个元素并指定为currSum。如果lastSum小于 0，则将i元素本身指定为currSum。旧值currSum现在称为lastSumlastPos&currPos保存各自总和值的最新索引。在下面显示的每次迭代的所有状态中，最右边的和表示currSum迭代开始时。左侧的值currSum表示lastSum。它们的索引位置分别记录在currPos&lastPos中。par[]保存使用的最后一个索引的值lastSum。该数组稍后用于构造形成最大非相邻和的实际元素集。initiallyidx = -1,&nbsp; 0,&nbsp; 1, 2,&nbsp; 3,&nbsp; 4, 5, 6arr =&nbsp; 0,&nbsp; 1,&nbsp; 2, 3, -1, -3, 2, 5sum =&nbsp; 0&nbsp; &nbsp;1par =&nbsp; &nbsp; &nbsp;-1i=1 iteration stateidx = -1,&nbsp; 0,&nbsp; 1, 2,&nbsp; 3,&nbsp; 4, 5, 6arr =&nbsp; 0,&nbsp; 1,&nbsp; 2, 3, -1, -3, 2, 5sum =&nbsp; 0&nbsp; &nbsp;1,&nbsp; ?par =&nbsp; &nbsp; &nbsp;-1,&nbsp; !// before updatecurrSum = 1, currPos = 0lastSum = 0, lastPos = -1// updatingpar[1] = lastPos = -1probableSum = max(2 + 0, 2)&nbsp; = 2 // max(arr[i] + lastSum, arr[i])? = max(1, 2) = 2 // max(currSum, probableSum)! = i = 1// after updatelastSum = currSum = 1lastPos = currPos = 0currSum = ? = 2currPos = ! = 1i=2 iteration stateidx = -1,&nbsp; 0,&nbsp; 1, 2,&nbsp; 3,&nbsp; 4, 5, 6arr =&nbsp; 0,&nbsp; 1,&nbsp; 2, 3, -1, -3, 2, 5sum =&nbsp; 0&nbsp; &nbsp;1,&nbsp; 2&nbsp; ?par =&nbsp; &nbsp; &nbsp;-1, -1&nbsp; !// before updatecurrSum = 2, currPos = 1lastSum = 1, lastPos = 0// updatingpar[2] = lastPos = 0probableSum = max(3 + 1, 3) = 4 // max(arr[i] + lastSum, arr[i])? = max(2, 4) = 4 // max(currSum, probableSum)! = i = 2// after updatelastSum = currSum = 2lastPos = currPos = 1currSum = ? = 4currPos = ! = 2i = 3 iteration stateidx = -1,&nbsp; 0,&nbsp; 1, 2,&nbsp; 3,&nbsp; 4, 5, 6arr =&nbsp; 0,&nbsp; 1,&nbsp; 2, 3, -1, -3, 2, 5sum =&nbsp; 0&nbsp; &nbsp;1,&nbsp; 2&nbsp; 4&nbsp; &nbsp;?par =&nbsp; &nbsp; &nbsp;-1, -1&nbsp; 0&nbsp; &nbsp;!// before updatecurrSum = 4, currPos = 2lastSum = 2, lastPos = 1//updatingpar[3] = lastpos = 1probableSum = 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 updatelastSum = currSum = 4lastPos = currPos = 2currSum = ? = 4currPos = ! = 2i = 4 iterationidx = -1,&nbsp; 0,&nbsp; 1, 2,&nbsp; 3,&nbsp; 4, 5, 6arr =&nbsp; 0,&nbsp; 1,&nbsp; 2, 3, -1, -3, 2, 5sum =&nbsp; 0&nbsp; &nbsp;1,&nbsp; 2&nbsp; 4&nbsp; &nbsp;4&nbsp; &nbsp;?par =&nbsp; &nbsp; &nbsp;-1, -1&nbsp; 0&nbsp; &nbsp;1&nbsp; &nbsp;!// before updatecurrSum = 4, currPos = 2lastSum = 4, lastPos = 2// updatingpar[4] = lastPos = 2probableSum = 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 updatelastSum = currSum = 4lastPos = currPos = 2currPos = ? = 4currPos = ! = 2i = 5 iterationidx = -1,&nbsp; 0,&nbsp; 1, 2,&nbsp; 3,&nbsp; 4, 5, 6arr =&nbsp; 0,&nbsp; 1,&nbsp; 2, 3, -1, -3, 2, 5sum =&nbsp; 0&nbsp; &nbsp;1,&nbsp; 2&nbsp; 4&nbsp; &nbsp;4&nbsp; &nbsp;4&nbsp; ?par =&nbsp; &nbsp; &nbsp;-1, -1&nbsp; 0&nbsp; &nbsp;1&nbsp; &nbsp;2&nbsp; !// before updatecurrSum = 4, currPos = 2lastSum = 4, lastPos = 2// updatingpar[5] = lastPos = 2probableSum = max(2 + 4, 2) = 6 // max(arr[i] + lastSum, arr[i])? = max(4, 6) = 6 // max(currSum, probableSum)! = i = 5// after updatelastSum = currSum = 4lastPos = currPos = 2currPos = ? = 6currPos = ! = 5i = 6 iteration stateidx = -1,&nbsp; 0,&nbsp; 1, 2,&nbsp; 3,&nbsp; 4, 5, 6arr =&nbsp; 0,&nbsp; 1,&nbsp; 2, 3, -1, -3, 2, 5sum =&nbsp; 0&nbsp; &nbsp;1,&nbsp; 2&nbsp; 4&nbsp; &nbsp;4&nbsp; &nbsp;4&nbsp; 6&nbsp; ?par =&nbsp; &nbsp; &nbsp;-1, -1&nbsp; 0&nbsp; &nbsp;1&nbsp; &nbsp;2&nbsp; 2&nbsp; !// before updatecurrSum = 6, currPos = 5lastSum = 4, lastPos = 2// updatingpar[6] = lastPos = 2probableSum = max(5 + 4, 5) = 9 // max(arr[i] + lastSum, arr[i])? = max(6, 9) = 9 // max(currSum, probableSum)! = i = 6// after updatelastSum = currSum = 6lastPos = currPos = 5currPos = ? = 9currPos = ! = 6after all iteration stateidx = -1,&nbsp; 0,&nbsp; 1, 2,&nbsp; 3,&nbsp; 4, 5, 6arr =&nbsp; 0,&nbsp; 1,&nbsp; 2, 3, -1, -3, 2, 5sum =&nbsp; 0&nbsp; &nbsp;1,&nbsp; 2&nbsp; 4&nbsp; &nbsp;4&nbsp; &nbsp;4&nbsp; 6&nbsp; 9par =&nbsp; &nbsp; &nbsp;-1, -1&nbsp; 0&nbsp; &nbsp;1&nbsp; &nbsp;2&nbsp; 2&nbsp; 2通过使用 par[] 并循环直到 par[p] != -1 我们可以获得元素的索引，它实际上形成了一组实际需要的元素。直接查看代码。例如p = last = 6arr[p] = arr[6] = 5 // elementp = par[p] = par[6] = 2arr[p] = arr[2] = 3 // elementp = par[p] = par[2] = 0arr[p] = arr[0] = 1 // elementp = par[p] = par[0] = -1 // stop

Answer 2

我更喜欢士官长的解决方案，但这是另一种方法：/** returns a list of indices which contain the elements that make up the max sum */public static List<Integer> maxSum(int arr[]) {&nbsp; &nbsp; int priorMaxSum = 0;&nbsp; &nbsp; List<Integer> priorMaxSumList = new ArrayList<>();&nbsp; &nbsp; // initial max sum&nbsp; &nbsp; int maxSum = arr[0];&nbsp; &nbsp; List<Integer> maxSumList = new ArrayList<>();&nbsp; &nbsp; maxSumList.add(0);&nbsp; &nbsp; for (int i = 1; i < arr.length; i++) {&nbsp; &nbsp; &nbsp; &nbsp; final int currSum;&nbsp; &nbsp; &nbsp; &nbsp; final List<Integer> currSumList;&nbsp; &nbsp; &nbsp; &nbsp; if (priorMaxSum > 0) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; // if the prior sum was positive, then continue from it&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; currSum = priorMaxSum + arr[i];&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; currSumList = new ArrayList<>(priorMaxSumList);&nbsp; &nbsp; &nbsp; &nbsp; } else {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; // if the prior sum was not positive, then throw it out and start new&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; currSum = arr[i];&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; currSumList = new ArrayList<>();&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; currSumList.add(i);&nbsp; &nbsp; &nbsp; &nbsp; // update prior max sum and list&nbsp; &nbsp; &nbsp; &nbsp; priorMaxSum = maxSum;&nbsp; &nbsp; &nbsp; &nbsp; priorMaxSumList = new ArrayList<>(maxSumList);&nbsp; &nbsp; &nbsp; &nbsp; if (currSum > maxSum) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; // update max sum&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; maxSum = currSum;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; maxSumList = currSumList;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; return maxSumList;}public static void main(String[] args) throws Exception {&nbsp; &nbsp; int[] a = {1, 2, 3, -5, -3, 2, 5};&nbsp; &nbsp; List<Integer> l = maxSum(a);&nbsp; &nbsp; System.out.println(&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; "indices {" + l.stream().map(String::valueOf).collect(Collectors.joining(", ")) + "}");&nbsp; &nbsp; System.out.println("values&nbsp; {"&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; + l.stream().map(i -> String.valueOf(a[i])).collect(Collectors.joining(", ")) + "}");}