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

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){

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

在循环结束时lastSum添加到第ith 个元素并指定为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

Answer 2

我更喜欢士官长的解决方案，但这是另一种方法：

/** 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(", ")) + "}");

}