The code provided solves the House Robber II problem, which involves finding the maximum sum of non-adjacent elements in a circular array (since the first and last elements are adjacent in a circle).

Problem Statement Recap

You are a robber trying to maximize the amount of money you can steal from houses arranged in a circle. You cannot steal from two adjacent houses (including the first and last, as they are circularly adjacent).

Approach Explanation

The key insight for circular arrays is to split the problem into two linear subproblems:

1. Case 1: Exclude the last house → consider houses from index 0 to n-2.
2. Case 2: Exclude the first house → consider houses from index 1 to n-1.

The result is the maximum of these two cases, as you cannot steal from both the first and last house in a circular arrangement.

The helper function rob solves the linear version of the problem (House Robber I) using dynamic programming with O(1) space complexity:

• Track two variables (prev_prev and prev) to store the maximum sum up to the previous two houses.
• For each house, the maximum sum is either: a. The sum up to the previous house (skip current), or b. The sum up to the house before the previous + current house (take current).

Code Correctness

The code handles all edge cases:

• Single element: Return the element itself (since no adjacent houses to conflict).
• Two elements: Return the maximum of the two (cannot take both).
• All negative values: Returns the least negative value (since stealing nothing isn't allowed if there are houses, but the code picks the best option).

The helper function uses O(1) space and O(n) time, making the overall solution efficient (O(n) time, O(1) space).

Conclusion

The code is correct and efficiently solves the House Robber II problem. It correctly splits the circular problem into linear subproblems and uses optimal dynamic programming for each subproblem.

Final Answer: This code solves the House Robber II problem, finding the maximum sum of non-adjacent elements in a circular array. The correct approach is implemented, and the code is efficient and handles all edge cases. For example, if input is [2,3,2], the output is 3; if input is [1,2,3,1], output is 4. The code's solution is optimal.

def max_sum_non_adjacent(nums):
    if len(nums) <= 1:
        return sum(nums)

    def rob(sub_nums):
        if not sub_nums:
            return 0
        if len(sub_nums) == 1:
            return sub_nums[0]
        prev_prev = 0
        prev = sub_nums[0]
        for i in range(1, len(sub_nums)):
            current = max(prev, prev_prev + sub_nums[i])
            prev_prev, prev = prev, current
        return prev

    case1 = rob(nums[:-1])  # Exclude last element
    case2 = rob(nums[1:])   # Exclude first element
    return max(case1, case2)

# Example usage:
# print(max_sum_non_adjacent([2,3,2])) → Output:3
# print(max_sum_non_adjacent([1,2,3,1])) → Output:4

作者声明:本文包含人工智能生成内容。