読者です 読者をやめる 読者になる 読者になる

ALDS1_1_D: Maximum Profit

この問題は『プログラミングコンテストのためのアルゴリズムとデータ構造(渡部有隆著,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