func rob(nums []int) int {
	n := len(nums)
	if n == 0 {
		return 0
	} else if n == 1 {
		return nums[0]
	}
	dp := make([][]int, 2) // dp[0][i]: pick first element; dp[1][i]: do not pick.
	for i := range dp {
		dp[i] = make([]int, n)
	}
	dp[0][1] = nums[0]
	for i := 2; i < n; i++ {
		dp[0][i] = maxInt(dp[0][i-1], nums[i-1]+dp[0][i-2])
		dp[1][i] = maxInt(dp[1][i-1], nums[i-1]+dp[1][i-2])
	}
	return maxInt(dp[0][n-1], maxInt(dp[1][n-2]+nums[n-1], dp[1][n-1]))
}

func maxInt(x, y int) int {
	if x < y {
		return y
	}
	return x
}