Maximum sum from non-adjacent subsequence

Given an array of positive numbers, find the maximum sum of a subsequence such that the elements in the sequence should not be adjacent to each other.

Example

Input: arr[] = {1, 2, 3, 4, 5}

Output: 9

Explanation: The maximum sum subsequence without adjacent elements is {1, 3, 5}, resulting in a sum of 9.

Example

Input: arr[] = {10, 20, 15, 25, 30}

Output: 55

Explanation: The maximum sum subsequence without adjacent elements is {10, 15, 30}, resulting in a sum of 55.

Approach

Iterate through the array, considering each element either included or excluded from the subsequence. At each step, we calculate the maximum sum considering the current element either included or excluded, based on the previously computed values. By dynamically updating these values as we progress through the array, we eventually find the maximum sum satisfying the given conditions.

Algorithm

1. Start by initializing two variables, include and exclude, to track the maximum sum considering the current element either included or excluded.
2. Loop through the array, starting from the second element.
3. For each element, calculate two new values:

1. newInclude: The sum of the current element and the exclude value from the previous step.
2. newExclude: The maximum of the previous include and exclude values.

4. Update the include and exclude variables with the new values calculated in the previous step.
5. Continue iterating through the array until you reach the end.
6. After processing all elements, the maximum sum will be the maximum of the final include and exclude values.
7. Return the maximum sum as the result.

Complexity

• Time Complexity: O(N), where N is the size of the array.
• Space Complexity: O(1)

Code

## Java Code

public class HouseRobber {
    public static int maxRobberyAmount(int[] houses) {
        int includeCurrentHouse = houses[0]; // Maximum amount if the current house is included
        int excludeCurrentHouse = 0; // Maximum amount if the current house is excluded

        // Iterate through the array starting from the second house
        for (int i = 1; i < houses.length; i++) {
            // Calculate the maximum amount if the current house is included
            int newInclude = excludeCurrentHouse + houses[i];
            // Calculate the maximum amount if the current house is excluded
            int newExclude = Math.max(includeCurrentHouse, excludeCurrentHouse);

            // Update includeCurrentHouse and excludeCurrentHouse for the next iteration
            includeCurrentHouse = newInclude;
            excludeCurrentHouse = newExclude;
        }

        // Return the maximum amount among includeCurrentHouse and excludeCurrentHouse
        return Math.max(includeCurrentHouse, excludeCurrentHouse);
    }

    public static void main(String[] args) {
        int[] houses1 = {1, 2, 3, 4, 5};
        System.out.println("Maximum amount that can be robbed: " + maxRobberyAmount(houses1));

        int[] houses2 = {10, 20, 15, 25, 30};
        System.out.println("Maximum amount that can be robbed: " + maxRobberyAmount(houses2));
    }
}

Output

Maximum sum: 9
Maximum sum: 55