题解 | #打家劫舍(二)#

分治法：将问题分为两种可能的情形处理，收集分类信息和处理每一种情形都只可以利用打家劫舍（一）的算法完成。

n = int(input())
nums = list(map(int, input().strip().split()))

# 处理输入极短的情况，避免指针越界
if len(nums) == 1:
    print(nums[0])
elif len(nums) in [2,3]:
    print(max(nums))
elif len(nums) == 4:
    print(max(nums[0]+nums[2], nums[1]+nums[3]))

# 主要情况
else:
    a,b = nums[0:2]
    for i in range(2,n-1):
        a,b = b,max(a+nums[i],b)
    b0 = b

	# Case 1：最后一家恰好不会被偷
    if a+nums[-1] <= b:
        print(b)
    
    # Case 2: 最后一家会被偷，此时第1家和最后2家是否被偷都已确定，
    # 问题从环状列表转化为顺序列表
    else:
        num = nums[-1]
        nums = nums[1:-1]
        a,b = nums[0:2]
        for i in range(2,n-3):
            a,b = b,max(a+nums[i],b)
        print(max(b+num, b0))