（備忘録）問題解決のための「アルゴリズム数学」〜 10

問題

atcoder.jp

回答

これは比較的分かりやすかったですね

N = gets.to_i
A = gets.split.map(&:to_i)

# i日目に勉強するdp1, i日目に勉強しないdp2の配列を用意する
dp1 = Array.new(N+1, 0)
dp2 = Array.new(N+1, 0)


(0...N).each do |i|
  dp1[i+1] = dp2[i] + A[i]
  dp2[i+1] = [dp1[i], dp2[i]].max
end

puts [dp1[N], dp2[N]].max