打家劫舍【二】

题目：你是一个经验丰富的小偷，准备偷沿湖的一排房间，每个房间都存有一定的现金，为了防止被发现，你不能偷相邻的两家，即，如果偷了第一家，就不能再偷第二家，如果偷了第二家，那么就不能偷第一家和第三家。沿湖的房间组成一个闭合的圆形，即第一个房间和最后一个房间视为相邻。
给定一个长度为n的整数数组nums，数组中的元素表示每个房间存有的现金数额，请你计算在不被发现的前提下最多的偷窃金额。

解题思路：计算前n-1个最大不相邻数的和与后n-1个最大不相邻数的和，然后再比较取最大。

#include <iostream>
using namespace std;

int main() {
    int n, res = 0;
    cin >> n;
    int arr[n], dp[n];
    for (int i = 0; i < n; ++i) cin >> arr[i];
    // 时间复杂度O(N)，空间复杂度O(N)
    dp[0] = arr[0], dp[1] = max(dp[0], arr[1]);
    for (int i = 2; i < n - 1; ++i) dp[i] = max(dp[i - 2] + arr[i], dp[i - 1]);
    res = dp[n - 2];

    dp[0] = 0, dp[1] = arr[1];
    for (int i = 2; i < n; ++i) dp[i] = max(dp[i - 2] + arr[i], dp[i - 1]);
    res = max(res, dp[n - 1]);
    cout << res;
    return 0;
}