CODEWITHSUNDEEP
arraysdynamic-programming
Rustam Ibragimov
Rustam Ibragimov

Reputation: 2707

Maximum array sum

I am given an array of integers. I need to find max sum of its elements so that any two elements are not neighbors. Example : sum(2, 5, 2) = 5 because we choose just 5; sum(3, 10, 2, 4, 10) = 20 because we choose 10 and 10; sum(10, 12, 5, 2) = 15 because we choose 10 and 5. How can it be done using any programming language? I have been working on this problem for several hours and the only thing I understand that it should use DP.

Upvotes: 1

Views: 460

Answers (1)

Luigi Procopio
Luigi Procopio

Reputation: 51

So I've implemented a solution in Java without using DP; I've simply used recursion. I'll try to explain it a bit.

First of all, we have to find a base case:

  • if the array length is == 1, then sum(array) = array[0]
  • besides, if the array length is == 2, then sum(array) = max(array[0],array[1])

Now, let's get to the general case of array.length = n. We have to decide whether or not array[n-1] is part of the solution; that is, if sum, launched on the first n-1 elements, is smaller than sum launched on the first n-2 elements + nth element of the array.

In a nutshell, we are saying "Is it better to consider the nth element or its neighbour (nth-1)?" Indeed, we cannot consider both, therefore we have to choose one.

private static int sum (int[] array) {
    return aux (array,array.length);
}
private static int aux (int[] array, int upTo) {

    if (upTo == 1)
        return array[0];
    else if (upTo == 2)
        return (array[1] > array[0]) 
                ? array[1] : array[0];
    else {
        int tmpMax1 = aux (array,upTo-1);
        int tmpMax2 = aux (array,upTo-2) + array[upTo-1];

        return (tmpMax2 > tmpMax1)
                ? tmpMax2 : tmpMax1;
    }
}

public static void main(String[] args) {
    //just a bunch of simple tests. Too lazy to use JUnit
    System.out.println(sum(new int[]{2}) + " = 2");
    System.out.println(sum(new int[]{2, 5}) + " = 5");
    System.out.println(sum(new int[]{2, 5, 2}) + " = 5");
    System.out.println(sum(new int[]{3, 10, 2, 4, 10}) + " = 20");
    System.out.println(sum(new int[]{10, 12, 5, 2}) + " = 15");
    System.out.println(sum(new int[]{10, 12, 5, 2,100}) + " = 115");
    System.out.println(sum(new int[]{10, 10, 10, 10,100}) + " = 120");

}

Upvotes: 1

Related Questions