[Dynamic Programming] Maximum Sum of Non-Adjacent Numbers in a Circle - Medium

The problem of finding the biggest sum of non-adjacent numbers in a circle is about getting the highest possible sum from a list of numbers. We cannot pick two numbers that are next to each other. We usually solve this using dynamic programming. This method helps us to break the problem into smaller parts. But since we have a circle, we must pay special attention to the first and last numbers in the list.

In this article, we will look at the best ways to find the biggest sum of non-adjacent numbers in a circle. We will explain the problem in detail, show a dynamic programming method, and give examples in Java, Python, and C++. We will also compare different methods, try to make the space we use smaller, and check different test cases and edge cases. At the end, we will answer some common questions about this topic.

  • [Dynamic Programming] Maximum Sum of Non-Adjacent Numbers in a Circle - Optimal Solutions
  • Understanding the Problem Statement for Maximum Sum of Non-Adjacent Numbers in a Circle
  • Dynamic Programming Approach for Maximum Sum of Non-Adjacent Numbers
  • Java Implementation of Maximum Sum of Non-Adjacent Numbers in a Circle
  • Python Code Example for Maximum Sum of Non-Adjacent Numbers
  • C++ Solution for Maximum Sum of Non-Adjacent Numbers in a Circle
  • Comparative Analysis of Different Approaches for Maximum Sum of Non-Adjacent Numbers
  • Optimizing Space Complexity in the Dynamic Programming Solution
  • Test Cases and Edge Cases for Maximum Sum of Non-Adjacent Numbers
  • Frequently Asked Questions

Understanding the Problem Statement for Maximum Sum of Non-Adjacent Numbers in a Circle

The problem of finding the Maximum Sum of Non-Adjacent Numbers in a Circle is like the classic “House Robber” problem. The main difference is that the numbers are in a circle. This makes it harder to decide which numbers we can pick without being next to each other.

Problem Definition

We have an array of integers. These integers show amounts of money and they are arranged in a circle. Our job is to find the maximum sum we can get by picking numbers that are not next to each other. The main rules are:

  • We cannot take two adjacent numbers (houses).
  • The first and last numbers are next to each other because they are in a circle.

Input and Output

  • Input: An array nums of integers where 1 <= nums.length <= 100.
  • Output: An integer that shows the maximum sum of non-adjacent numbers.

Example

For the input array nums = [2, 3, 2]: - The maximum sum can be 3 (we do not pick the 2 next to it) or 2 (not the first 2). - The maximum sum here is 3.

For another input nums = [1, 2, 3, 1]: - We can pick 1 and 3 to get a maximum sum of 4.

Approach

To solve this problem well, we can use a dynamic programming method. We will compute the maximum sums for two cases: 1. Exclude the first element. 2. Exclude the last element.

This helps us look at all possible ways while following the rules about adjacency.

Dynamic Programming Recurrence Relation

Let dp[i] be the maximum sum we can get from the first i elements. We can write the relation like this:

  • dp[i] = max(dp[i-1], nums[i] + dp[i-2])

In this, dp[i-1] means we do not take the current element. While nums[i] + dp[i-2] means we take it, so we skip the adjacent element.

Constraints Handling

  • If the input array has only one element, we return that element.
  • If there are two elements, we return the bigger one.

This way of working makes sure we cover all special cases while finding the maximum sum in a circle.

Dynamic Programming Approach for Maximum Sum of Non-Adjacent Numbers

We will solve the problem of finding the maximum sum of non-adjacent numbers in a circle. We use a dynamic programming approach. The circular way the numbers are arranged makes adjacency tricky.

Problem Breakdown

  1. Linear vs Circular: First, we treat the circular array as two separate linear problems. If we pick the first element, we can’t take the last one. And if we take the last one, we can’t take the first one.

  2. Dynamic Programming State: We define the state dp[i] as the maximum sum from the first i numbers. We need to ensure no two selected numbers are next to each other.

  3. Transition Formula: We define the transition like this:

    • dp[i] = max(dp[i-1], dp[i-2] + nums[i])
    • This means for each number, we can either:
      • Skip it (take the maximum sum up to the previous number).
      • Include it (add it to the maximum sum two numbers before).

  4. Base Cases:

    • dp[0] = nums[0]
    • dp[1] = max(nums[0], nums[1])

Implementation Steps

  1. We will implement the logic for the two cases:
    • Case 1: Exclude the last number.
    • Case 2: Exclude the first number.
  2. Then we compute the maximum of both cases to get the final answer.

Java Implementation

Here is how we can do this in Java:

public class MaxSumNonAdjacent {
    public int rob(int[] nums) {
        if (nums.length == 1) return nums[0];
        return Math.max(robLinear(Arrays.copyOfRange(nums, 0, nums.length - 1)),
                        robLinear(Arrays.copyOfRange(nums, 1, nums.length)));
    }

    private int robLinear(int[] nums) {
        int prev1 = 0, prev2 = 0;
        for (int num : nums) {
            int temp = prev1;
            prev1 = Math.max(prev1, prev2 + num);
            prev2 = temp;
        }
        return prev1;
    }
}

Python Code Example

Here is the same logic in Python:

def rob(nums):
    def rob_linear(nums):
        prev1, prev2 = 0, 0
        for num in nums:
            temp = prev1
            prev1 = max(prev1, prev2 + num)
            prev2 = temp
        return prev1

    if len(nums) == 1:
        return nums[0]
    
    return max(rob_linear(nums[:-1]), rob_linear(nums[1:]))

# Example usage
nums = [2, 3, 2]
print(rob(nums))  # Output: 3

C++ Solution

Here is how we can do this in C++:

class Solution {
public:
    int rob(vector<int>& nums) {
        if (nums.size() == 1) return nums[0];
        return max(robLinear(vector<int>(nums.begin(), nums.end() - 1)),
                   robLinear(vector<int>(nums.begin() + 1, nums.end())));
    }

    int robLinear(vector<int>& nums) {
        int prev1 = 0, prev2 = 0;
        for (int num : nums) {
            int temp = prev1;
            prev1 = max(prev1, prev2 + num);
            prev2 = temp;
        }
        return prev1;
    }
};

These implementations help us find the maximum sum of non-adjacent numbers in a circle using dynamic programming. It is clear and works well. For more on dynamic programming, you can check articles on Dynamic Programming: Maximum Sum of Non-Adjacent Elements or Dynamic Programming: House Robber Problem.

Java Implementation of Maximum Sum of Non-Adjacent Numbers in a Circle

To solve the problem of finding the maximum sum of non-adjacent numbers in a circle using Java, we can use dynamic programming. We need to think about the circle by looking at two cases. One case is when we do not take the first number. The other case is when we do not take the last number.

Here is the Java code:

public class MaximumSumNonAdjacentCircle {
    
    public static int maxSumNonAdjacent(int[] nums) {
        if (nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];
        if (nums.length == 2) return Math.max(nums[0], nums[1]);

        return Math.max(maxSumLinear(Arrays.copyOfRange(nums, 0, nums.length - 1)),
                        maxSumLinear(Arrays.copyOfRange(nums, 1, nums.length)));
    }

    private static int maxSumLinear(int[] nums) {
        int include = 0, exclude = 0;
        
        for (int num : nums) {
            int newExclude = Math.max(include, exclude);
            include = exclude + num;
            exclude = newExclude;
        }
        
        return Math.max(include, exclude);
    }

    public static void main(String[] args) {
        int[] nums = {2, 3, 2};
        System.out.println("Maximum sum of non-adjacent numbers in a circle: " + maxSumNonAdjacent(nums));
    }
}

Explanation of the Code:

  • maxSumNonAdjacent: This method splits the problem into two smaller problems by ignoring either the first or the last number.
  • maxSumLinear: This helper method uses a simple dynamic programming method to find the maximum sum of non-adjacent numbers in a straight array.
  • Variables include and exclude keep track of sums when we include or exclude the current number we are looking at.

Example:

For the input array [2, 3, 2], the output is 3. This is because the maximum sum of non-adjacent numbers comes from picking 3.

This code efficiently finds the maximum sum while keeping the adjacency rule in mind. It also works well with the circular nature of the input array. If we want to learn more about dynamic programming, we can look at similar problems like Maximum Sum of Non-Adjacent Elements.

Python Code Example for Maximum Sum of Non-Adjacent Numbers

We will solve the problem of finding the maximum sum of non-adjacent numbers in a circular array using Python. We can use dynamic programming for this. The main idea is to think about two choices: including the first element or not including it. This is like the “House Robber” problem but a bit more tricky because the array is circular.

def max_non_adjacent_sum(arr):
    if not arr:
        return 0
    n = len(arr)
    if n == 1:
        return arr[0]
    if n == 2:
        return max(arr[0], arr[1])

    # Helper function to calculate the maximum sum in a linear array
    def linear_max_sum(nums):
        include = 0
        exclude = 0
        for num in nums:
            new_exclude = max(include, exclude)
            include = exclude + num
            exclude = new_exclude
        return max(include, exclude)

    # Exclude the last element and include the first
    case1 = linear_max_sum(arr[:-1])
    # Exclude the first element and include the last
    case2 = linear_max_sum(arr[1:])
    
    return max(case1, case2)

# Example usage
arr = [2, 3, 2]
print(max_non_adjacent_sum(arr))  # Output: 3

Explanation:

The function max_non_adjacent_sum takes an array as input. It checks some special cases for arrays of size 0, 1, and 2.

The helper function linear_max_sum finds the maximum sum of non-adjacent numbers in a regular array using dynamic programming.

We look at two situations. One is where we take the first element and skip the last element. The other is where we skip the first element and take the last element.

In the end, we return the highest value from these two situations.

This Python code shows a dynamic programming method to find the maximum sum of non-adjacent numbers in a circular array. It helps us manage the rules of not picking adjacent numbers.

C++ Solution for Maximum Sum of Non-Adjacent Numbers in a Circle

We have a problem. We want to find the maximum sum of non-adjacent numbers in a circular array with C++. We can use a simple method called dynamic programming. The circular shape of the array makes it tricky. We need to think about two cases. One is when we include the first element. The other is when we don’t include it.

Approach

  1. Base Cases:
    • If the array length is 0, we return 0.
    • If the array length is 1, we return the first element.
    • If the array length is 2, we return the bigger of the two elements.
  2. Dynamic Programming Logic:
    • We will use a helper function. This function will find the maximum sum for a normal linear array. We think about two scenarios:
      • We include the first element and we exclude the last element.
      • We exclude the first element and we include the last element.
  3. Dynamic Programming Array:
    • We keep a dp array. Here dp[i] stores the maximum sum of non-adjacent numbers up to index i.

C++ Code Implementation

#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

int maximumNonAdjacentSum(const vector<int>& nums, int start, int end) {
    int prev1 = 0, prev2 = 0;
    for (int i = start; i < end; ++i) {
        int temp = max(prev1, prev2 + nums[i]);
        prev2 = prev1;
        prev1 = temp;
    }
    return prev1;
}

int maxSumNonAdjacentInCircle(const vector<int>& nums) {
    int n = nums.size();
    if (n == 0) return 0;
    if (n == 1) return nums[0];
    if (n == 2) return max(nums[0], nums[1]);

    // Case 1: Include the first element, exclude the last
    int case1 = maximumNonAdjacentSum(nums, 0, n - 1);
    // Case 2: Exclude the first element, include the last
    int case2 = maximumNonAdjacentSum(nums, 1, n);
    
    return max(case1, case2);
}

int main() {
    vector<int> nums = {2, 3, 2};
    cout << "Maximum sum of non-adjacent numbers in a circle: " 
         << maxSumNonAdjacentInCircle(nums) << endl;
    return 0;
}

Explanation of the Code

  • Function maximumNonAdjacentSum:
    • This function takes a part of the array. It finds the maximum sum of non-adjacent elements using dynamic programming.
  • Function maxSumNonAdjacentInCircle:
    • This function calls maximumNonAdjacentSum two times. It handles both cases of the circular array. Then it returns the biggest result.

This C++ solution works well. It finds the maximum sum of non-adjacent numbers in a circular array. It takes time O(n) and uses space O(1). It does not need much extra space.

For more learning about dynamic programming, you can look at Dynamic Programming - Maximum Sum of Non-Adjacent Elements.

Comparative Analysis of Different Approaches for Maximum Sum of Non-Adjacent Numbers

We want to find the maximum sum of non-adjacent numbers in a circle. There are many ways to do this. Each way has its own pros and cons. These include time complexity, space complexity, and how hard they are to implement. Here, we look at some popular methods.

1. Dynamic Programming Approach

We often use the dynamic programming method for this problem. It breaks the problem into smaller pieces. We store results to avoid doing the same work again.

  • Time Complexity: O(n)
  • Space Complexity: O(n) or O(1) if we make it better

We treat the array as circular. We can change our dynamic programming method to fit this shape. We have two cases to solve:

  • Skip the first element
  • Skip the last element

This gives us two separate linear problems that we can combine later.

Java Implementation

public class MaxSumNonAdjacent {
    public int maxSum(int[] nums) {
        if (nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];
        
        return Math.max(maxSumNonAdjacent(nums, 0, nums.length - 2),
                        maxSumNonAdjacent(nums, 1, nums.length - 1));
    }
    
    private int maxSumNonAdjacent(int[] nums, int start, int end) {
        int prev = 0, curr = 0;
        for (int i = start; i <= end; i++) {
            int temp = curr;
            curr = Math.max(prev + nums[i], curr);
            prev = temp;
        }
        return curr;
    }
}

Python Implementation

def max_sum_non_adjacent(nums):
    if not nums:
        return 0
    if len(nums) == 1:
        return nums[0]

    def helper(start, end):
        prev, curr = 0, 0
        for i in range(start, end + 1):
            new_curr = max(prev + nums[i], curr)
            prev = curr
            curr = new_curr
        return curr

    return max(helper(0, len(nums) - 2), helper(1, len(nums) - 1))

C++ Implementation

class Solution {
public:
    int rob(vector<int>& nums) {
        if (nums.empty()) return 0;
        if (nums.size() == 1) return nums[0];

        auto helper = [](vector<int>& nums, int start, int end) {
            int prev = 0, curr = 0;
            for (int i = start; i <= end; ++i) {
                int temp = curr;
                curr = max(prev + nums[i], curr);
                prev = temp;
            }
            return curr;
        };

        return max(helper(nums, 0, nums.size() - 2), helper(nums, 1, nums.size() - 1));
    }
};

2. Recursive Approach with Memoization

We can also use recursion with memoization. This means we save results of states we have already solved. This makes things quicker.

  • Time Complexity: O(n)
  • Space Complexity: O(n) because of the recursion stack

This method can be slower in real life. This is because of the extra work needed for recursive calls. But it helps us understand the problem better.

3. Iterative Approach

We can use an iterative way too. It is like dynamic programming but with less focus on past states. This method keeps only the last two sums we calculated.

  • Time Complexity: O(n)
  • Space Complexity: O(1)

This method is great when we need to save memory.

Conclusion

When we want to solve the maximum sum of non-adjacent numbers in a circle, we suggest using the dynamic programming method. It is efficient and clear. If you want to learn more about dynamic programming, check out Dynamic Programming - Maximum Sum of Non-Adjacent Elements.

Optimizing Space Complexity in the Dynamic Programming Solution

When we solve the problem of finding the maximum sum of non-adjacent numbers in a circular array using dynamic programming, it is important to optimize space complexity. This helps improve performance, especially when the input size is large.

Space Optimization Technique

The usual dynamic programming solution keeps an array to store results. But we only need the last two values at any time. So we can cut down the space complexity from O(n) to O(1).

Code Implementation

Here is how we can implement the space-optimized solution in Java, Python, and C++:

Java Implementation:

public class MaxSumNonAdjacent {
    public int getMaxSum(int[] nums) {
        if (nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];
        
        int include = nums[0]; // Max sum including the previous number
        int exclude = 0; // Max sum excluding the previous number
        
        for (int i = 1; i < nums.length; i++) {
            int newInclude = exclude + nums[i]; // Include current number
            exclude = Math.max(include, exclude); // Update exclude
            include = newInclude; // Update include
        }
        
        return Math.max(include, exclude); // Return max of include or exclude
    }
}

Python Implementation:

def get_max_sum(nums):
    if not nums:
        return 0
    if len(nums) == 1:
        return nums[0]
    
    include = nums[0]
    exclude = 0
    
    for num in nums[1:]:
        new_include = exclude + num
        exclude = max(include, exclude)
        include = new_include
    
    return max(include, exclude)

C++ Implementation:

class Solution {
public:
    int getMaxSum(vector<int>& nums) {
        if (nums.empty()) return 0;
        if (nums.size() == 1) return nums[0];
        
        int include = nums[0];
        int exclude = 0;
        
        for (int i = 1; i < nums.size(); i++) {
            int new_include = exclude + nums[i];
            exclude = max(include, exclude);
            include = new_include;
        }
        
        return max(include, exclude);
    }
};

Key Points

  • Space Complexity: The optimized solution runs in O(1) space. It uses only a few variables to track current include and exclude values.
  • Time Complexity: The time complexity stays O(n). Here, n is the number of elements in the array. This ensures fast computation.
  • Applicability: This optimization is very helpful in competitive programming and situations with limited memory.

For more reading on similar dynamic programming problems, we can check this article on the maximum sum of non-adjacent elements.

Test Cases and Edge Cases for Maximum Sum of Non-Adjacent Numbers

To check if our solution for finding the maximum sum of non-adjacent numbers in a circular array works well, we need to look at many test cases and edge cases. These cases help us to see if our solution can handle different situations correctly.

Basic Test Cases

  1. Simple Case
    • Input: [2, 4, 6, 2]
    • Expected Output: 8 (We select 2 and 6)
  2. Single Element
    • Input: [5]
    • Expected Output: 5 (There is only one element)
  3. Two Elements
    • Input: [1, 2]
    • Expected Output: 2 (We can only choose one)
  4. Three Elements
    • Input: [1, 2, 3]
    • Expected Output: 4 (We pick 1 and 3)
  5. All Negative Numbers
    • Input: [-1, -2, -3, -4]
    • Expected Output: -1 (We choose the least negative number)

Edge Cases

  1. Empty Array
    • Input: []
    • Expected Output: 0 (No elements to choose)
  2. Large Numbers
    • Input: [1000, 2000, 3000, 4000]
    • Expected Output: 6000 (We pick 2000 and 4000)
  3. Alternating High-Low Values
    • Input: [5, 1, 5, 1, 5]
    • Expected Output: 15 (We choose all 5s)
  4. High Values with Low Non-Adjacent
    • Input: [10, 1, 10, 1, 10]
    • Expected Output: 30 (We select all 10s)
  5. Circular Case
    • Input: [1, 2, 3, 1]
    • Expected Output: 4 (We take 1 and 3, not 2)

Performance Testing

  1. Large Array
    • Input: [i for i in range(1, 10001)]
    • Expected Output: Should work fast without timeouts.
  2. Maximum Size Input with Randomized Values
    • Input: Randomly made array of size 10^6.
    • Expected Output: Check performance and correctness.

Implementation Considerations

  • We must make sure that the algorithm deals with circular references well. This is important when the first and last elements have a conflict.
  • We need to check that the dynamic programming method uses memoization or tabulation correctly to make it fast.

These test cases and edge cases are very important to check how strong and correct our algorithm is for the maximum sum of non-adjacent numbers in a circle problem. For more information on similar dynamic programming tasks, you can visit Dynamic Programming - Maximum Sum of Non-Adjacent Elements.

Frequently Asked Questions

1. What is the maximum sum of non-adjacent numbers in a circular array?

We want to find the maximum sum of numbers in a circle. We can only pick numbers that are not next to each other. This means we need to be careful with the first and last numbers in the array. They can change what numbers we can pick. For more details and answers, look at our guide on the maximum sum of non-adjacent numbers.

2. How does dynamic programming help solve the maximum sum of non-adjacent numbers problem?

Dynamic programming helps us solve the maximum sum of non-adjacent numbers by breaking the problem into smaller parts. We keep track of the best sum we can get at each step. We also make sure that we do not pick adjacent numbers. For a full explanation, check our section on the dynamic programming approach for maximum sums.

3. Can you provide a Python solution for the maximum sum of non-adjacent numbers in a circle?

Sure! A common Python solution uses dynamic programming to save the best sums at each spot. The algorithm looks at two cases: one that does not take the last number and one that does not take the first number. For full code, you can see our Python code example section here.

4. What are the key differences between the linear and circular versions of the maximum sum problem?

In the linear version, we can pick from a straight list. But in the circular version, we must think about the first and last numbers because they are next to each other. In the circular case, we find the maximum sums in two ways: one without the first number and one without the last number. A good comparison can help us understand this dynamic programming problem better.

5. What are some test cases for the maximum sum of non-adjacent numbers in a circle?

We should test this problem with different cases. This includes all positive numbers, a mix of positive and negative numbers, and small arrays like those with 2 or 3 elements. Testing with a circular array makes sure we check both ends well. You can find more test cases and examples in our section on maximum sum of non-adjacent numbers.