ALGORITHM NOTE ヒストグラム中の最大の長方形の面積データの離散型分布を表すヒストグラム（柱状グラフ）は、長方形を共通の基線上に並べた多角形として描画されます。これらの長方形は同じ幅を持ちますが、異なる高さのものを含みます。ヒストグラムを表す多角形に含まれる最大の長方形の面積を求めて下さい。入力は各データに対応する長方形の高さの列に対応した n 個の要素からなる１次元配列とします。(source: ACM/ICPC University of Ulm Local Contest) 以下のように、２重ループによって長方形の範囲を選び、そこにできる最大の長方形の面積を計算して更新していけば、全体での最大の面積を求めることができます。これはO(n2)のアルゴリズムです。 001 int getRectangleAreaBF( int size, int buffer[] ){ 002 int maxv = 0; 003 for ( int i =
