题解 | 打家劫舍(二)

#include <bits/stdc++.h>
using namespace std;

long long robLinear(const vector<int>& a, int l, int r) { // 闭区间 [l,r]
    long long prev2 = 0, prev1 = 0; // dp[i-2], dp[i-1]
    for (int i = l; i <= r; ++i) {
        long long cur = max(prev1, prev2 + (long long)a[i]);
        prev2 = prev1;
        prev1 = cur;
    }
    return prev1;
}

int main() {
    int n;
    cin >> n;
    vector<int> nums(n);
    for (int i = 0; i < n; ++i) cin >> nums[i];

    if (n == 1) {
        cout << nums[0] << '\n';
        return 0;
    }
    cout << max(robLinear(nums, 0, n - 2), robLinear(nums, 1, n - 1)) << '\n';
    return 0;
}