"""
p56 — House Robber (LeetCode 198, MEDIUM).

dp[i] = max(dp[i-1], dp[i-2] + nums[i])
"""
from __future__ import annotations
import random
from typing import List


def rob_dp_array(nums: List[int]) -> int:
    n = len(nums)
    if n == 0:
        return 0
    if n == 1:
        return nums[0]
    dp = [0] * n
    dp[0] = nums[0]
    dp[1] = max(nums[0], nums[1])
    for i in range(2, n):
        dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])
    return dp[-1]


def rob_o1_space(nums: List[int]) -> int:
    # INVARIANT: prev2 = best up to i-2; prev1 = best up to i-1.
    prev2 = prev1 = 0
    for x in nums:
        prev2, prev1 = prev1, max(prev1, prev2 + x)
    return prev1


def rob_brute(nums: List[int]) -> int:
    # Try every subset, validate non-adjacency. Exponential.
    n = len(nums)
    best = 0
    for mask in range(1 << n):
        ok = True
        total = 0
        prev = -2
        for i in range(n):
            if mask & (1 << i):
                if i - prev == 1:
                    ok = False
                    break
                total += nums[i]
                prev = i
        if ok:
            best = max(best, total)
    return best


def edge_cases() -> None:
    assert rob_o1_space([]) == 0
    assert rob_o1_space([5]) == 5
    assert rob_o1_space([5, 3]) == 5
    assert rob_o1_space([1, 2, 3, 1]) == 4
    assert rob_o1_space([2, 7, 9, 3, 1]) == 12
    assert rob_o1_space([2, 1, 1, 2]) == 4
    assert rob_o1_space([0, 0, 0]) == 0
    assert rob_dp_array([1, 2, 3, 1]) == 4
    print("edge_cases: PASS")


def stress_test() -> None:
    rng = random.Random(42)
    for trial in range(500):
        n = rng.randint(0, 15)
        nums = [rng.randint(0, 20) for _ in range(n)]
        a = rob_o1_space(nums)
        b = rob_dp_array(nums)
        c = rob_brute(nums)
        assert a == b == c, f"trial {trial}: nums={nums} a={a} b={b} c={c}"
    print("stress_test: 500 trials — o1, dp_array, brute agree.")


if __name__ == "__main__":
    edge_cases()
    stress_test()
    print("ALL TESTS PASSED")