C++ 算法：最大非相邻数之和

问题描述

给定一个包含 N 个正整数的数组，每个整数的值在 1 到 300 之间。你需要从数组中选择若干个数，要求选择的数不能相邻，并且要求选择的数的总和最大。

例如：

当 N = 5 时，数组中的 5 个数字分别为：13, 18, 28, 45, 21。

在这种情况下，有很多种取法，例如：

13, 28, 21，总和为 62
13, 45，总和为 58
18, 45，总和为 63

总和为 63 的取法满足要求。

输入描述

第一行是一个整数 N，表示数组的长度。第二行包含 N 个正整数，表示数组中的元素。

输出描述

输出一个整数，表示选择的数的最大和。

算法实现

可以使用动态规划 (DP) 算法来解决这个问题。

C++ 代码：

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int N;
    cin >> N;

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

    // 创建一个长度为N的dp数组，dp[i]表示以第i个数结尾的最大和
    vector<int> dp(N);

    // 初始化dp数组的前两个元素
    dp[0] = nums[0];
    dp[1] = max(nums[0], nums[1]);

    for (int i = 2; i < N; i++) {
        // 状态转移方程：dp[i] = max(dp[i-1], dp[i-2]+nums[i])
        dp[i] = max(dp[i-1], dp[i-2]+nums[i]);
    }

    cout << dp[N-1] << endl;

    return 0;
}

解释：

dp 数组: 我们使用一个长度为 N 的 dp 数组来存储信息。dp[i] 表示以第 i 个数结尾的子序列的最大和。
初始化: 我们初始化 dp[0] 为第一个数字，dp[1] 为第一个数字和第二个数字中的较大者。
状态转移方程: 对于 i 大于等于 2 的情况，我们可以选择两种情况：
- 不选择第 i 个数，此时最大和为 dp[i-1]；
- 选择第 i 个数，此时最大和为 dp[i-2]加上第 i 个数。
结果: dp[N-1] 表示以最后一个数字结尾的子序列的最大和，也就是最终的结果。

总结

本算法使用动态规划 (DP) 方法来有效地解决从数组中选择非相邻数以获得最大和的问题。通过状态转移方程，我们可以逐步计算出以每个数字结尾的最大和，最终得出问题的解。