using System; using System.Linq; namespace Program { class Program { static void Main() { int count = int.Parse(Console.ReadLine()); int[] aji = Console.ReadLine().Split(' ').Select(int.Parse).ToArray(); Dp m_dp = new Dp(aji, count); Console.WriteLine(m_dp.GetMax().ToString()); Console.ReadLine(); } } class Dp { private int[,] _dp = new int[1000, 2]; private int[] _aji; private int _saraCount; public Dp(int[] aji, int saracount) { _saraCount = saracount; _aji = aji; _dp[0, 0] = 0; _dp[0, 1] = _aji[0]; } public int GetMax() { if (_saraCount == 1) { return _aji[0]; } _dp[1, 0] = _dp[0, 1]; _dp[1, 1] = _aji[1] + _dp[0, 0]; for (int count = 2; count < _saraCount; count++) { _dp[count, 0] = Math.Max(_dp[count - 1, 1], _dp[count - 2, 1]); _dp[count, 1] = _aji[count] + Math.Max(_dp[count - 1, 0], _dp[count - 2, 0]); } return Math.Max(_dp[_saraCount - 1, 0], _dp[_saraCount - 1, 1]); } } }