Maximum sum of non adjacent elements of an array,

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;
}

Examples :

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

回答1:

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];
    }
}

I believe code can be cleaned up a lot, but that's an exercise for later :)

Output:

{1,2,3,-1,-3,2,5} => 5 3 1

{4,5,4,3} => 3 5

Update. Added some code explanation

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.

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.

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 holds latest index of thier respective sum values.

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[] 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

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.

e.g.

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

回答2:

I like Master Chief's solution better but here's another approach:

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