AOJ ALDS1_1_D Maximum Profit

効率化していく過程がなるほどなーと思ったのでメモ。

AOJ > コース > Algorithms and Data Structures I > Getting Started > "Maximum Profit" ←イマココ

問題

自然数列Rに対して、R_j - R_i ( j > i ) の最大値を求めよ。

解法

部分点解法

愚直に求めるなら、各jに対して、jより小さいiをすべて試せばよい。

N = int(input())
a = []
for i in range(N):
    a.append(int(input()))
mx = -10**12
for j in range(1, N):
    for i in range(j):
        mx = max(mx, a[j] - a[i])
print(mx)

しかしこれだと計算量がO(n²)なので、nが大きいと間に合わない。

満点解法

R_j - R_i ( j > i ) が最大となるのは、R_i が j番目より前の要素の中で最小の要素であるときである。ならば先にi番目までの最小値を配列に記憶しておけば、各jに対しO(1)の計算ですむ。最小値の記録はO(n), jに対するループもO(n)だから全体でO(n)となる。

N = int(input())
a = []
for i in range(N):
    a.append(int(input()))
 
mins = [a[0]]
for i in range(1, N):
    mins.append(min(a[i], mins[i-1]))
     
mx = -10**12
for j in range(1, N):
    mx = max(mx, a[j] - mins[j-1])
print(mx)

これで一応ACするが、実は最小値を記録しておく必要はない。各jに対し、j-1番目までの最小値が分かればよいので、入力を受け取りながらmaxとminの計算を同時に行っていけばよい。

N = int(input())
 
#R[0]
minv = int(input())
maxv = -10**12
 
#R[1..N-1]
for j in range(1, N):
    r = int(input())
    maxv = max(maxv, r - minv)
    minv = min(minv, r)
     
print(maxv)

以上3つの解答をsubmitした結果が下図。O(n²)だとTLEしていることと、O(n)のコードのうち後者の方がメモリ使用量が少ないことがわかる。