問題 108 Maximum Sum
難易度 投稿数 15675 (正解率 42.1 %)

NXN の行列から、最大値をもつサブ行列を求める問題。

計算時間を意識しないといけない。O(N6) のプログラム、つまり for文を 6重に使う解答では、計算時間オーバーでパスできない。

O(N3) のアルゴリズムもあるみたいだが、O(N4) のものに思いつき、投稿したら accepted になった。

配列を沢山取り、ひたすら加算する。計算時間の稼ぎに、メモリ資源を使う。こういう戦略だった。

Comments are closed.

Post Navigation