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

给定一个整数数组 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];
}