プログラミングコンテスト攻略のためのアルゴリズムとデータ構造
p46 の Maximum Profit
Jは最大値を探せばいいからn回探索になる。
Jから左側の最小値を記憶しておけば良い。＜＜この発想ができる事が鍵。
毎回最小値を探しに行かなくてよくなる。
計算量はこれでO(n)となる。
これは特殊な番兵問題だろうか？
SublimeText3でC++を気軽に実行する環境を作る。 - Qiita
sablime txt3からの実行では入力ができないので手動入力部分をコメントアウトした。
#include "iostream"
// #include "algorithm"
using namespace std;
// static const int MAX = 200000;
int main()
{
/* 手動入力
int R[MAX],n;
cin >> n;
for (int i = 0; i < i < n; ++i) {
cin >> R[i];
}
*/
const int n = 6;
int R[n]={5,3,1,3,4,3};
int maxv = R[1] - R[0];
int minv = R[0];
for (int j = 1; j < n; ++j) {
maxv = max(maxv, R[j] - minv);
minv = min(minv, R[j]);
}
cout << maxv << endl;
return 0;
}
| 入力 | 出力 |
|---|---|
| 6個 | 利益 3 |
| R[0] = 5 | |
| R[1] = 3 | |
| R[2] = 1 | |
| R[3] = 3 | |
| R[4] = 4 | |
| R[5] = 3 |
maxv R[1]-R[0] = -2(もしくは-10^9以下)
minv R[0] = 5 R[j]の最小値
R[j]よりも左側の最小値を記憶しておく。
それをR[j]の最高値から引けば答えが出る。
アルゴリズム
Jを1からn-1まで（＝全部調べる）
maxv maxvとR[j]-minvの大きい方＜＜利益
minv minvとR[j]のうち小さい方
| j | R | maxv | minv |
|---|---|---|---|
| R[0] = 5 | -2 | 5 | |
| 1 | R[1] = 3 | -2 | 3 |
| 2 | R[2] = 1 | -2 | 1 |
| 3 | R[3] = 3 | 2 | 1 |
| 4 | R[4] = 4 | 3 | 1 |
| 5 | R[5] = 3 | 3 | 1 |
参考図書
プログラミングコンテスト攻略のためのアルゴリズムとデータ構造
すぐに理解できなかったのでメモ。
いまだに２重ループになると、どの数値がどのように動くのか瞬時に理解できない、これは回数を重ねて問題を解くしか無い・・orz。