N = gets.to_i V = gets.split.map(&:to_i) case V.size when 1, 2 puts V.max exit when 3 puts [V[0]+V[2], V[1]].max exit end dp = Array.new(N+1){ -1 } dp[0] = 0 dp[1] = V[0] dp[2] = V[1] dp[3] = V[0] + V[2] 4.upto(N) do | i | dp[i] = dp[i-3] > dp[i-2] ? dp[i-3] + V[i-1] : dp[i-2] + V[i-1] end p dp[-1]