ALDS1_1_D: Maximum Profit

AOJ AOJ本

この問題は『プログラミングコンテストのためのアルゴリズムとデータ構造（渡部有隆著，Ozy・秋葉拓哉協力）』を読んで解きました．

　

問題

　

ソースコード

#include <stdio.h>

int main()
{
    int i;

    //入力
    int n;
    scanf("%d", &n);
    int R[n];
    for( i = 0; i < n; ++i )
        scanf("%d", &R[i]);

    //minが最小になるようにmaxを選ぶ
    int min = R[0], max = R[1] - R[0];
    for( i = 1; i < n; ++i ){
        max = max < R[i] - min ? R[i] - min : max;
        min = min > R[i] ? R[i] : min; //minは後から更新しないと R[i]-min == min-min になる
    }

    printf("%d\n", max);

    return 0;
}

　

反省点

  • 二重for文を回して全部チェックするもTLE
  • 最小値を求めてから，最小値よりも添字が大きい部分で最大値を探して max - min をしたらWA
  • 諦めて解説を読む
  • これまでの最小値と現在の値の差の最大値を求めてAC