题解 | #不相邻取数#

#include <iostream>
#include <vector>
using namespace std;
int main(){
    int N;
    while(cin >> N){
        vector<int> nums;
        while(N--){
            int n;
            cin >> n;
            nums.push_back(n);
        }
        // 1、确定dp数组含义：假设dp[i]是包含nums[i]在内的不相邻数之和；
        // 2、确定状态转移方程：dp[i] = max(dp[i-2] + nums[i], dp[i-3]+nums[i])
        // 最后输出最大的dp即可
        vector<int> dp(nums.size());
        int max_sum = INT16_MIN;
        for(int i = 0; i < nums.size(); ++i){
            if (i == 0 || i == 1) dp[i] = nums[i];
            if (i == 2) dp[i] = dp[i-2] + nums[i];
            if (i >= 3) dp[i] = max(dp[i-2] + nums[i], dp[i-3]+nums[i]);
            max_sum = max(dp[i], max_sum);
        }
        cout << max_sum << endl;
    }
    return 0;
}