Max Subset Sum No Adjacent

Write a function that takes in an array of positive integers and returns the maximum sum of non-adjacent elements in the array.

If the input array is empty, the function should return 0.

Sample input

[75, 105, 120, 75, 90, 135]

Sample output

330 = 75 + 120 + 135

Solution

Time Complexity: O(n)

Space Complexity: O(1)

static int maxSubsetSumNoAdjacent(int[] array) {

    int answer = 0;

    if (array.length == 0) {
        return 0;
    } else if (array.length == 1) {
        return array[0];
    }

    int first = Math.max(array[0], array[1]);
    int second = array[0];
    int current = 0;
    

    for (int i = 2; i < array.length; i++) {
        current = Math.max(first, second + array[i]);
        second = first;
        first = current;

    }

    answer = first;

    return answer;
}

 

Source code on Github




Subscribe To Our Newsletter
You will receive our latest post and tutorial.
Thank you for subscribing!

required
required


Leave a Reply

Your email address will not be published.