In this coding challenge, you are asked to create a Java program that calculates the maximum sum of non-adjacent elements in a given array. The array will consist of integers and can have both positive and negative numbers. Your program should be able to handle arrays of varying lengths.

Problem Statement

Given an array of integers, find the maximum sum that can be obtained by adding non-adjacent elements. Non-adjacent elements are elements that are not immediate neighbors in the array. The goal is to maximize the sum while ensuring that no two selected elements are adjacent to each other.

Input

An array of integers arr (1 ≤ |arr| ≤ 10^5) where each element arr[i] (-10^4 ≤ arr[i] ≤ 10^4) represents an integer in the array. Output:

Return an integer that represents the maximum sum of non-adjacent elements in the given array.

Constraints

The input array may have both positive and negative numbers. The input array may have duplicate elements. The input array may be of any length, within the given limits. If the input array is empty, the output should be 0. Example: Consider the following array: [2, 4, 6, 2, 5]. The maximum sum of non-adjacent elements would be 13, which comes from adding 2, 6, and 5.

Notes

In this problem, you are not required to provide a solution. Instead, focus on providing a clear and detailed description of the problem statement and requirements.

Sample Inputs

1. Input: [2, 4, 6, 2, 5] Output: 13 (2 + 6 + 5)

2. Input: [5, 1, 1, 5] Output: 10 (5 + 5)

3. Input: [-1, -2, -3, -4, -5] Output: -1 (-1)

4. Input: [3, 2, 7, 10] Output: 13 (3 + 10)

5. Input: [1, 0, 3, 9, 2] Output: 10 (1 + 9)

6. Input: [1, 2, 3, 4, 5, 6, 7, 8, 9] Output: 25 (1 + 3 + 5 + 7 + 9)

7. Input: [] Output: 0

8. Input: [5, -2, 7, 10, -5, 3] Output: 18 (5, 10, 3)

9. Input: [3, 5, -1, 2, 6, 8, 4, -3] Output: 15 (5, 2, 8)

10. Input: [100, 200, 300, 400, 500] Output: 900 (100 + 300 + 500)

Steps

Step 1: Initialize two variables, inclusive and exclusive

Description: Before we start iterating through the input array, we need to initialize two variables, inclusive and exclusive. Both of these variables will be used to keep track of the maximum sum of non-adjacent elements in the array.

• inclusive: This variable stores the maximum sum that includes the current element while iterating through the array. It will be updated at each step by adding the current element to the previous value of exclusive.
• exclusive: This variable stores the maximum sum that does not include the current element while iterating through the array. It will be updated at each step by taking the maximum of the previous values of inclusive and exclusive.

Initially, both inclusive and exclusive are set to 0, as we have not yet considered any elements in the array.

Code Example:

public int maxSumNonAdjacent(int[] arr) {
    int inclusive = 0;
    int exclusive = 0;

    // The rest of the code will go here
}

In this code example, we have a function maxSumNonAdjacent that takes an integer array arr as input. We initialize the variables inclusive and exclusive to 0 before proceeding with the next steps of the algorithm.

Step 2: Iterate through the input array from the beginning to the end

Description: In this step, we will iterate through the input array, updating the values of inclusive and exclusive at each step. This is done to maintain the maximum sum of non-adjacent elements while considering the inclusion or exclusion of the current element.

a. For each element in the array, calculate the new inclusive sum by adding the current element to the exclusive sum. This is because, to include the current element, we should not include the previous element (as they are adjacent). Therefore, the new inclusive sum is the exclusive sum from the previous step plus the current element.

b. Update the exclusive sum to be the maximum of the previous inclusive sum and the previous exclusive sum. This is because the new exclusive sum should not include the current element, but can include any element before the current element in the array.

c. Update the inclusive sum to the value calculated in step 2a. This ensures that the inclusive sum always reflects the maximum sum when including the current element in the array.

Code Example:

public int maxSumNonAdjacent(int[] arr) {
    int inclusive = 0;
    int exclusive = 0;

    for (int i = 0; i < arr.length; i++) {
        int tempInclusive = inclusive; // Store the previous value of inclusive
        int tempExclusive = exclusive; // Store the previous value of exclusive

        // Calculate the new inclusive sum
        inclusive = tempExclusive + arr[i];

        // Update the exclusive sum
        exclusive = Math.max(tempInclusive, tempExclusive);
    }

    // The rest of the code will go here
}

In this code example, we iterate through the input array arr using a for loop. At each iteration, we store the previous values of inclusive and exclusive in temporary variables, tempInclusive and tempExclusive. We then update the inclusive sum by adding the current element to tempExclusive and update the exclusive sum by taking the maximum of tempInclusive and tempExclusive.

Step 3: Determine the maximum sum of non-adjacent elements

Description: After iterating through the input array and updating the inclusive and exclusive sums, we need to determine the maximum sum of non-adjacent elements. Since the inclusive sum represents the maximum sum that includes the last element of the array, and the exclusive sum represents the maximum sum that does not include the last element of the array, we can find the overall maximum sum by taking the maximum of these two sums.

Code Example:

public int maxSumNonAdjacent(int[] arr) {
    int inclusive = 0;
    int exclusive = 0;

    for (int i = 0; i < arr.length; i++) {
        int tempInclusive = inclusive; // Store the previous value of inclusive
        int tempExclusive = exclusive; // Store the previous value of exclusive

        // Calculate the new inclusive sum
        inclusive = tempExclusive + arr[i];

        // Update the exclusive sum
        exclusive = Math.max(tempInclusive, tempExclusive);
    }

    // Determine the maximum sum of non-adjacent elements
    int maxSum = Math.max(inclusive, exclusive);

    return maxSum;
}

In this code example, after the for loop, we calculate the maximum sum of non-adjacent elements by taking the maximum of the final inclusive and exclusive sums. We store this value in the variable maxSum and return it as the result of the maxSumNonAdjacent function.

Step 4: Return the result as an integer

Description: Once we have determined the maximum sum of non-adjacent elements in the input array by comparing the final values of inclusive and exclusive, we need to return this value as the output of our function. The result should be an integer representing the maximum sum that can be obtained by adding non-adjacent elements from the given input array.

Code Example:

public int maxSumNonAdjacent(int[] arr) {
    int inclusive = 0;
    int exclusive = 0;

    for (int i = 0; i < arr.length; i++) {
        int tempInclusive = inclusive; // Store the previous value of inclusive
        int tempExclusive = exclusive; // Store the previous value of exclusive

        // Calculate the new inclusive sum
        inclusive = tempExclusive + arr[i];

        // Update the exclusive sum
        exclusive = Math.max(tempInclusive, tempExclusive);
    }

    // Determine the maximum sum of non-adjacent elements
    int maxSum = Math.max(inclusive, exclusive);

    // Return the result as an integer
    return maxSum;
}

In this code example, the final step is already included in the previous steps. The variable maxSum, which holds the maximum sum of non-adjacent elements, is returned as the result of the maxSumNonAdjacent function. This integer value represents the solution to the problem as per the given problem statement and constraints.

Time Complexity (Big-O)

The Big-O notation is used to describe the performance of an algorithm by analyzing its time and space complexity as a function of the input size. For this problem, we have implemented a dynamic programming solution to find the maximum sum of non-adjacent elements in an array.

Time Complexity: O(n)

The time complexity of the given solution is O(n), where n represents the number of elements in the input array. This is because we iterate through the input array once using a single for loop. In each iteration, the operations performed (updating variables, creating new lists, and adding elements) take constant time, which does not depend on the size of the array. Therefore, the overall time complexity is linear with respect to the input size.

Space Complexity: O(n)

The space complexity of this solution is also O(n), mainly due to the storage of the inclusiveElements and exclusiveElements lists, which store the elements involved in the maximum sum. In the worst case, these lists will store n/2 elements each (when every other element is included in the solution), resulting in a total storage of n elements. Apart from these lists, there is a constant amount of space used for storing integer variables and temporary lists. Therefore, the overall space complexity is linear with respect to the input size.

In summary, the Big-O of this problem is O(n) for both time and space complexity, making it an efficient solution for finding the maximum sum of non-adjacent elements in an array.

Conclusion

Here’s the final program with a main method that runs all of the sample test cases:

public class MaxSumNonAdjacent {

    public static int maxSumNonAdjacent(int[] arr) {
        int inclusive = 0;
        int exclusive = 0;

        for (int i = 0; i < arr.length; i++) {
            int tempInclusive = inclusive; // Store the previous value of inclusive
            int tempExclusive = exclusive; // Store the previous value of exclusive

            // Calculate the new inclusive sum
            inclusive = tempExclusive + arr[i];

            // Update the exclusive sum
            exclusive = Math.max(tempInclusive, tempExclusive);
        }

        // Determine the maximum sum of non-adjacent elements
        int maxSum = Math.max(inclusive, exclusive);

        // Return the result as an integer
        return maxSum;
    }

    public static void main(String[] args) {
        int[][] testCases = {
            {2, 4, 6, 2, 5},
            {5, 1, 1, 5},
            {-1, -2, -3, -4, -5},
            {3, 2, 7, 10},
            {1, 0, 3, 9, 2},
            {1, 2, 3, 4, 5, 6, 7, 8, 9},
            {},
            {5, -2, 7, 10, -5, 3},
            {3, 5, -1, 2, 6, 8, 4, -3},
            {100, 200, 300, 400, 500}
        };

        int[] expectedOutputs = {
            13,
            10,
            -1,
            13,
            10,
            25,
            0,
            18,
            15,
            900
        };

        for (int i = 0; i < testCases.length; i++) {
            int[] testCase = testCases[i];
            int expectedResult = expectedOutputs[i];
            int actualResult = maxSumNonAdjacent(testCase);

            System.out.printf("Test case %d: %s%n", i + 1, actualResult == expectedResult ? "PASSED" : "FAILED");
            System.out.printf("Expected: %d, Actual: %d%n%n", expectedResult, actualResult);
        }
    }
}

In this program, we have added a main method that runs all of the sample test cases provided earlier. The testCases array contains the input arrays for each test case, and the expectedOutputs array contains the expected results for each test case. We then loop through the test cases, calling the maxSumNonAdjacent function with each input array, and comparing the results with the expected outputs. If the actual result matches the expected result, we print “PASSED”, otherwise we print “FAILED”, along with the expected and actual results for each test case.

Extension: Print the integers contained within the solution

Here’s a modified version of the program that not only finds the maximum sum of non-adjacent elements but also shows which integers are part of the solution:

import java.util.ArrayList;
import java.util.List;

public class MaxSumNonAdjacent {

    public static class Result {
        int maxSum;
        List<Integer> elements;

        public Result(int maxSum, List<Integer> elements) {
            this.maxSum = maxSum;
            this.elements = elements;
        }
    }

    public static Result maxSumNonAdjacent(int[] arr) {
        int inclusive = 0;
        int exclusive = 0;
        List<Integer> inclusiveElements = new ArrayList<>();
        List<Integer> exclusiveElements = new ArrayList<>();

        for (int i = 0; i < arr.length; i++) {
            int tempInclusive = inclusive; // Store the previous value of inclusive
            int tempExclusive = exclusive; // Store the previous value of exclusive
            List<Integer> tempInclusiveElements = new ArrayList<>(inclusiveElements);
            List<Integer> tempExclusiveElements = new ArrayList<>(exclusiveElements);

            // Calculate the new inclusive sum
            inclusive = tempExclusive + arr[i];
            inclusiveElements = new ArrayList<>(tempExclusiveElements);
            inclusiveElements.add(arr[i]);

            // Update the exclusive sum
            if (tempInclusive > tempExclusive) {
                exclusive = tempInclusive;
                exclusiveElements = new ArrayList<>(tempInclusiveElements);
            } else {
                exclusive = tempExclusive;
            }
        }

        // Determine the maximum sum of non-adjacent elements and the elements involved
        if (inclusive > exclusive) {
            return new Result(inclusive, inclusiveElements);
        } else {
            return new Result(exclusive, exclusiveElements);
        }
    }

    public static void main(String[] args) {
        int[][] testCases = {
            {2, 4, 6, 2, 5},
            {5, 1, 1, 5},
            {-1, -2, -3, -4, -5},
            {3, 2, 7, 10},
            {1, 0, 3, 9, 2},
            {1, 2, 3, 4, 5, 6, 7, 8, 9},
            {},
            {5, -2, 7, 10, -5, 3},
            {3, 5, -1, 2, 6, 8, 4, -3},
            {100, 200, 300, 400, 500}
        };

        int[] expectedOutputs = {
            13,
            10,
            -1,
            13,
            10,
            25,
            0,
            15,
            17,
            900
        };

        for (int i = 0; i < testCases.length; i++) {
            int[] testCase = testCases[i];
            int expectedResult = expectedOutputs[i];
            Result actualResult = maxSumNonAdjacent(testCase);

            System.out.printf("Test case %d: %s%n", i + 1, actualResult.maxSum == expectedResult ? "PASSED" : "FAILED");
            System.out.printf("Expected: %d, Actual: %d%n", expectedResult, actualResult.maxSum);
            System.out.printf("Elements involved: %s%n%n", actualResult.elements.toString());
        }
    }
}

In this modified version, we use an additional Result class to store both the maximum sum and the elements involved in the solution. We maintain two separate lists, inclusiveElements and exclusiveElements,