家の強盗
あなたはある通りに並んだ家からの強盗を計画しています。そこには
n 軒の家があり、それぞれから盗める金額がわかっています。ただし、防犯システムが作動し、同じ夜に隣り合う2軒の家を襲うと、自動的に警察へ通報されてしまいます。では、警察に捕まらずに一晩で手に入れられる最大の金額はいくらになるでしょうか？
入力
最初の行には、単一の整数
n (1 ≤ n ≤ ) が入力されます。次の行には、
n 個の整数 (1 ≤ ≤ ) がスペース区切りで与えられ、各家から盗める金額を表します。出力
捕まることなく得られる最大の金額を出力してください。
例
入力 | 出力 |
4
1 2 5 1 | 6 |
5
3 17 12 3 7 | 24 |
解説
- 1 + 5
- 17 + 7 （途中の家をいくつか飛ばしています）
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB