4308: DP23 不相邻取数
[Creator : ]
Description
小红拿到了一个数组。她想取一些不相邻的数，使得取出来的数之和尽可能大。你能帮帮她吗？
Input
第一行输入一个正整数 $n$，代表数组长度
第二行输入 $n$ 个正整数 $a_i$，代表整个数组。
Output
不相邻的数的最大和。
Constraints
$1≤n≤2∗10^5$
$1≤a_i≤5∗10^3$
$1≤a_i≤5∗10^3$
Sample 1 Input
4
2 6 4 1
Sample 1 Output
7
取 6 和 1 即可
Sample 2 Input
4
1 2 3 1
Sample 2 Output
4
偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 =1+3=4。
偷窃到的最高金额 =1+3=4。
Sample 3 Input
5
2 7 9 3 1
Sample 3 Output
12
偷窃 1 号房屋 (金额 =2)，偷窃 3 号房屋 (金额=9)，接着偷窃 5 号房屋 (金额=1)。
偷窃到的最高金额 =2+9+1=12。
偷窃到的最高金额 =2+9+1=12。
HINT
相同题目：牛客网，LeetCode 打家劫舍 I。