给定一个整数数组 a ,每个元素表示一个位置上的数值。要求从数组中选择若干个元素,使得任意两个被 选择的元素在原数组中都不相邻,并且所选元素的总和最大。函数 choose(vector<int>& a) 返回能够得到的最 大总和,则横线处应填写( )。

int choose(vector<int>& a) {
    if (a.empty()) return 0;
    int n = a.size();
    if (n == 1) return a[0];
    vector<int> dp(n, 0);
    dp[0] = a[0];
    dp[1] = max(a[0], a[1]);
    for (int i = 2; i < n; ++i) {
        dp[i] = __________________________;
    }
    return dp[n - 1];
}

{{ select(1) }}

• dp[i - 1] + a[i]
• max(dp[i - 1], dp[i - 2] + a[i])
• max(dp[i - 2], a[i])
• dp[i - 1] + dp[i - 2]