AOJ 0022 Maximum Sum Sequence 解説

OkNCT-ICT 2013 春合宿 Day 6 (らしい) に解説したもの.

Transcript

1. AOJ 0022 Maximum Sum Sequence 解説 @kagamiz
2. www.company.com 問題概要 • 長さがn の数列が与えられます. • 連続する1 個以上の項の和の最大値を求めてください. • n ≦ 5000 (Challenge ケースではn ≦ 10^6) • |ai| ≦ 100000
3. www.company.com 入力例の解析 • n = 7 数列 = {-5　-1　6　4　9　-6　-7} • 赤の部分列を選ぶと最適で, 和は19 になる. {-5　-1　6　4　9　-6　-7}
4. www.company.com 入力例の解析 • n = 13 数列 = {1　2　3　2　-2　-1　1　2　3　2　1　-2　1} • 赤の部分列を選ぶと最適で, 和は14 になる. {1　2　3　2　-2　-1　1　2　3　2　1　-2　1}
5. www.company.com 入力例の解析 • n = 3 数列 = {1000　-200　201} • 赤の部分列を選ぶと最適で, 和は1001 になる. {1000　-200　201}
6. www.company.com O(n^3) 解法 • すべての区間を試す. • 区間は左と右を決めれば一意に定まる ← O(n^2) 個 • 左から右までをfor 文で和を取る ← O(n)時間 • こうして調べた和の中の最大値が答え. • n ≦ 200 までならOK.
7. www.company.com O(n^2) 解法 • O(n^3) 解法の何が無駄だったか？ • どの区間が最大になるかはよく分からないか ら、O(n^2) 個すべてを試したい. • “左から右までをfor 文で和を取る ← O(n)時間” • これを高速にしよう
8. www.company.com O(n^2) 解法 • 累積和配列の利用. • S[i] = a[1] + a[2] + … + a[i] という配列を用意. • S[1] から順番に計算するとO(n) 時間で構築できる. • 区間[l, r] の和はS[r] – S[l – 1] で求まる. • よって, 2 重ループがもっとも重くO(n^2) 時間となる. • n ≦ 5000 までならOK.
9. www.company.com O(n) 解法 • Challenge ケースでも満点を取るためにはどうすれば 良いか？ → 動的計画法の利用. • dp[i] : 区間[x, i]での部分列の和の最大値(a[i] は必ず含 む)とすると, dp[i] = max(dp[i – 1] + a[i], a[i]) となる. • 答えはdp[i] の最大値. • 今までの最大値を利用するか, 自分から始めるか.
10. www.company.com O(n) 解法 • n = 13 数列 = {1　2　3　2　-2　-1　1　2　3　2　1　-2　1} dp[i]= {1　3　6　8　 6 5 6 8 11 13 14 12 13} • これは, for 文で最初から計算すると線形時間で求まる. • これで, Challenge ケースでも満点が取れる! • お疲れ様でした.