# Iterative DP with mem with n elements in DP variable
class Solution:
    def rob(self, nums: List[int]) -> int:

        n = len(nums)

        dp = [0]*(n)
        dp[0] = nums[0]
        if len(nums) == 1:
            return dp[0]
        dp[1] = max(dp[0], nums[1])
        if len(nums) == 2:
            return dp[1]

        max_so_far = -math.inf

        for i in range(2, n):
            dp[i] = max(dp[i-2] + nums[i], dp[i-1])

            # if there were negative elements as well
            # dp[i] = max(dp[i-2] + nums[i], dp[i-1], dp[i-2], nums[i])

            # relevant when there are negative numbers; but in general a good practice
            max_so_far = max(dp[i], max_so_far)

        return max_so_far

# Iterative DP with mem with n+2 elements in DP variable
class Solution:
    def rob(self, nums: List[int]) -> int:

        n = len(nums)

        dp = [0]*(n+2)
        max_so_far = -math.inf

        for i in range(2, n+2):
            dp[i] = max(dp[i-1], dp[i-2] + nums[i-2])

            # if there were negative elements as well
            # dp[i] = max(dp[i-2] + nums[i], dp[i-1], dp[i-2], nums[i])

            # relevant when there are negative numbers; but in general a good practice
            max_so_far = max(max_so_far, dp[i])

        return max_so_far

# Iterative without any extra space
class Solution:
    def rob(self, nums: List[int]) -> int:

        # prev2 = max_ending_here 2 iterations back
        # prev1 = max_ending_here 1 iteration back
        prev2 = 0
        prev1 = 0
        max_so_far = -math.inf

        for n in nums:
            # for the current number
            max_ending_here = max(prev2+n, prev1)

            # for the next loop
            prev2 = prev1
            prev1 = max_ending_here

            # relevant when there are negative numbers; but in general a good practice
            max_so_far = max(max_so_far, max_ending_here)

        return max_so_far