AIZU ONLINE JUDGE ALDS1_1_D - 今日から始める競プロ日記

はじめに

螺旋本に載っている問題を解いていこうと思う。

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造

今日は2.5導入問題（p. 46）の「ALDS1_1_D : 最大の利益」

https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/1/ALDS1_1_D

最大の利益

• ある通貨の時刻tにおける価格Rtが与えられる
• Rj - Ri（j > i）の最大値を求めよ

制約

2 <= N <= 2*10^5
1 <= Rt <= 10^9

解いた方針

単純に解こうとするとO(N^2)でTLE。

ちゃんと考えればO(N)で解けそう。

時系列の状態を維持する必要があるからソートはできないけど、 最安値は保持してもよさそうだということに気づく。

つまり、先頭から価格を順番に見ていった場合、 すでに見た価格は時系列とか関係なくなる。

だからすでに見た価格の中から最安値を見つけて保持。

あとは次にくる価格と差をとって最大値を更新していくだけ。

提出したコード

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    // 入力
    long long N; cin >> N;
    vector<long long> v(N);
    for(int i = 0; i < N; i++) cin >> v[i];
    // 計算
    long long ans = -(1<<30);
    long long minv = v[0];
    for(int i = 1; i < N; i++)
    {
        // 差を計算
        long long tmp = v[i] - minv;
        // 最大値を更新
        ans = max(ans, tmp);
        // 最安値を更新
        minv = min(minv, v[i]);
    }
    // 解を出力
    cout << ans << endl;
    return 0;
}

おわりに

良い問題。

今日から始める競プロ日記まとめ

kato-robotics.hatenablog.com