题目内容

小红有一个整数数组，现在他想从中选出一些数，使得这些数的和尽可能大。但是他不想同时选择数组中相邻的元素，问你有没有什么算法可以快速选出这些数。注意，小红是一个有追求的人，考虑到有 $n$ 个数，所以他要求算法能够在 $O(n)$ 的时间复杂度内算出答案。

思路

经典的线性DP问题。

$f[i]$ 表示只考虑前 $i$ 个数可以获得的最大值。

$f[0] = 0, f[1] = a[1]$

状态转移方程为：