题解 | #不相邻取数#

开始时使用暴力法，用一个三重循环枚举出所有可能的不相邻数的和，并选出其中最大的和作为输出
其核心思想是对每一种可能的间隔，每一种可能的起点，计算出其最大的和。由于数组元素非负，所以在起点与间隔固定的情况下，数字当然越多越好。
具体做法为，最外层循环控制间隔，间隔是从1~size()-2的。中间层循环控制起点，起点不同相加的数会不同。最内层循环来计算在当前间隔与起点的情况下的最大和。

这种做法的时间复杂度高达O(n^3)，所以在提交的第6个用例处超时。由于该用例数据量过大，无法查证是时间复杂度过高导致超时，还是出现死循环导致超时，这里暂且认为是因为时间复杂度过高。

#include <iostream>
#include <vector>

using namespace std;

int main(){
    int length;
    cin >> length;
    vector<long long> arr(length);
    for(int i = 0;i < length;i++){
        cin >> arr.at(i);
    }
    long long max = 0;
    for(int i = 1;i < arr.size() - 2;i++){
        for(int k = 0;k < i + 1;k++){
            long long sum = 0;
            for(int j = k;j < arr.size();j += i + 1){
                sum += arr.at(j);
            }
            max = sum > max ? sum : max;
        }
    }
    cout << max;
    return 0;
}

为了解决上面时间复杂度过高的问题，我们换一种思路。不再将所有可能的情况算出，而是使用类似前缀和的形式。
建立一个二维数组，用于保存前i个数中最大的不相邻数和。令arr为储存数字的数组，f(i)表示包含i的前i个数中最大的不相邻数和，g(i)表示不包含i的前i个数中最大的不相邻数和。则可以得到递推式，f(i)=g(i-1)+arr(i)，g(i)=max(f(i-1),g(i-1))。
得到递推式后，就可以选择使用递归或迭代的方法得到结果。下面选择使用迭代的方法，我们最终要求的是max(f(n),g(n))。

这种做法时间复杂度上远优于上面的做法，仅为O(n)，而空间复杂度为O(n)。
要注意的是这道题也有加和后可能发生int溢出的问题，所以保存数据的变量选择使用long long类型。

#include <iostream>
#include <vector>

using namespace std;

int main(){
    int length;
    cin >> length;
    vector<long long> arr(length);
    vector<long long> temp{2,0};
    vector<vector<long long>> res(length, temp);
    for(int i = 0;i < length;i++){
        cin >> arr.at(i);
    }
    long long max = 0;
    res.at(0).at(0) = 0;
    res.at(0).at(1) = arr.at(0);
    for(int i = 1;i < length;i++){
        res.at(i).at(0) = res.at(i - 1).at(0) > res.at(i - 1).at(1) ? res.at(i - 1).at(0) : res.at(i - 1).at(1);
        res.at(i).at(1) = res.at(i - 1).at(0) + arr.at(i);
    }
    cout << (res.at(length - 1).at(0) > res.at(length - 1).at(1) ? res.at(length - 1).at(0) : res.at(length - 1).at(1));
    return 0;
}