题目描述
给定一个长度为 n 的非负整数序列 a1,a2,…,an,你需要从中选出若干个数,使得任意两个被选中的数在原序列中的下标之差至少为 2。求所有满足条件的选法中,被选中数字之和的最大值。
形式化地,选出一个下标集合 S⊆{1,2,…,n},满足对任意 i,j∈S 且 i=j,都有 ∣i−j∣≥2,最大化 ∑i∈Sai。
注意:可以不选任何数,此时和为 0。
输入格式
第一行一个整数 n。
第二行 n 个非负整数 a1,a2,…,an,相邻两数用空格分隔。
输出格式
输出一行一个整数,表示满足条件的最大和。
样例
5
1 2 3 4 5
9
6
5 1 1 5 1 5
15
说明/提示
数据范围
- 对于 30% 的数据,1≤n≤20。
- 对于 60% 的数据,1≤n≤1000。
- 对于 100% 的数据,1≤n≤105,0≤ai≤109。
提示
设 fi 表示只考虑前 i 个数时能取得的最大和。若第 i 个数不选,答案为 fi−1;若选第 i 个数,则第 i−1 个数不能选,答案为 fi−2+ai。因此 fi=max(fi−1,fi−2+ai),边界 f0=0, f1=a1。答案即 fn。
解析
解题思路
题目要求选出若干下标,使任意两个被选下标之差至少为 2,并最大化选中数字之和。因为所有 ai 非负,所以虽然允许不选,但最优解不会因为“多选”而变差;不选只是状态转移中的一种选择。
考虑按序列顺序做决策。设 fi 表示只考虑前 i 个数时能取得的最大和。
对于第 i 个数,有两种情况:
- 不选第 i 个数:答案就是前 i−1 个数的最优值,即 fi−1。
- 选第 i 个数:由于相邻下标不能同时选,第 i−1 个数一定不能选,因此前面只能从 1∼i−2 中选,贡献为 fi−2+ai。
所以状态转移方程为:
fi=max(fi−1,fi−2+ai)
边界为 f0=0,f1=a1。最终答案为 fn。
算法选择理由
该问题具有明显的最优子结构:前 i 个数的最优解只依赖前 i−1 和前 i−2 个数的最优解,且无后效性。因此直接使用一维动态规划即可,不需要枚举子集或使用复杂数据结构。
复杂度分析
- 时间复杂度:O(n),只需一次线性扫描。
- 空间复杂度:O(n),可优化为 O(1),但 n≤105 时数组完全足够。
由于 ai≤109,答案可能达到 1014 级别,需要使用 long long 存储。
来源
AI 生成 · 云端大模型(域):deepseek-chat · 普及+/提高- · 动态规划