Problem:


  MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], processEscapes: true }});

Maximum Profit

You can obtain profits from foreign exchange margin transactions. For example,  if you buy 1000 dollar at a rate of 100 yen per dollar, and sell them at a rate of 108 yen per dollar, you can obtain (108 - 100) &times; 1000 = 8000 yen.

  Write a program which reads values of a currency $R_t$ at a certain time $t$ ($t = 0, 1, 2, ... n-1$), and reports the maximum value of $R_j - R_i$ where $j > i$ .

Input

The first line contains an integer $n$. In the following $n$ lines, $R_t$ ($t = 0, 1, 2, ... n-1$) are given in order.

Output

Print the maximum value in a line.

Constraints

  
$2 \leq n \leq 200,000$

  
$1 \leq R_t \leq 10^9$

Sample Input 1

6
5
3
1
3
4
3

Sample Output 1

3

Sample Input 2

3
4
3
2

Sample Output 2

-1



Sample input:
6
5
3
1
3
4
3


Sample output:
3

Submission status: Accepted

Solution code:
dif_max = 1-10**9
min = 10**9
n_max = 0
n_max = int(raw_input())
 
price = [0]*n_max
for i in range(0, n_max):
  price[i] = int(raw_input())
for i in range(0, n_max-1):
  if min >= price[i]:
      min = price[i]
  if dif_max <= price[i+1] - min:
      dif_max = price[i+1] - min
print dif_max

Submission status: Accepted

Solution code:
n = input()
maxi = -1 * 10**9
mini = input()


for i in range(n-1):
  tmp = input()
  maxi = max(maxi, tmp - mini)
  mini = min(mini, tmp)

print maxi

Submission status: Accepted

Solution code:
n = input()
n_max = -(10**9)
n_min = input() 

for i in range(0, n-1):
 R = input()
 if n_max < R - n_min:
  n_max = R - n_min
 if R < n_min:
  n_min = R
 
print n_max

Submission status: Accepted

Solution code:
n = int( raw_input( ) )
minv = int( raw_input( ) )
maxv = 0 - 1000000000
  
for j in range( n-1 ):
  num = int( raw_input( ) )  
  diff = num - minv
  if maxv < diff:
    maxv = diff
  if num < minv:
    minv = num
  
print maxv

Submission status: Accepted

Solution code:
n = int(raw_input())
minv = int(raw_input())
maxv = 0 - 1000000000
  
for j in range( n-1 ):
  num = int( raw_input( ) )  
  diff = num - minv
  if maxv < diff:
    maxv = diff
  if num < minv:
    minv = num
  
print maxv

Submission status: Accepted

Solution code:
n = int(raw_input())
minv = int(raw_input())
maxv = -1*10**9
  
for j in range( n-1 ):
  num = int( raw_input( ) )  
  diff = num - minv
  if maxv < diff:
    maxv = diff
  if num < minv:
    minv = num
  
print maxv

Submission status: Accepted

Solution code:
n = int(raw_input())
minv = int(raw_input())
maxv = -1*10**9
  
for j in range(n-1):
  num = int(raw_input())  
  diff = num - minv
  if maxv < diff:
    maxv = diff
  if num < minv:
    minv = num
  
print maxv

Submission status: Accepted

Solution code:
n = int(raw_input())
minv = int(raw_input())
maxv = -1*10**9
  
for j in range(n-1):
  nums = int(raw_input())  
  diff = nums - minv
  if maxv < diff:
    maxv = diff
  if nums < minv:
    minv = nums
  
print maxv

Submission status: Accepted

Solution code:
n = int(raw_input())
max = -(10**9)
x1 = input() 
min = x1

for i in range(n-1):
 x = int(raw_input())

 if max < x-min:
  max = x- min
 if x< min:
  min = x
  
print max

Submission status: Accepted

Solution code:
n = int(raw_input())
max = -10**9
x1 = input() 
min = x1

for i in range(n-1):
 x = int(raw_input())

 if max < x-min:
  max = x- min
 if x< min:
  min = x
  
print max

Submission status: Accepted

Solution code:
n = int(input())
DifMax = -9999999999999

R = [int(input())]
RMin = R[0]
for i in range(1, n):
  if RMin > R[i-1]:
      RMin = R[i-1]
  R.append(int(input()))
  if DifMax < R[i] - RMin:
    DifMax = R[i] - RMin

print(DifMax)

Submission status: Accepted

Solution code:
n = input()
R = [input() for i in xrange(n)]
m = R[0]
ans = -1e10
for r in R[1:]:
    ans = max(ans, r - m)
    m = min(m, r)
print ans

Submission status: Accepted

Solution code:
n = input()
R = [input() for i in range(n)]
m = R[0]
ans = -1e10
for r in R[1:]:
    ans = max(ans, r - m)
    m = min(m, r)
print ans

Submission status: Accepted

Solution code:
N = int(raw_input())
min = int(raw_input())
max = int(raw_input())

ans = max - min
if max < min:
    min = max
 
for i in range(N - 2):
    R = int(raw_input())
    if R - min > ans:
        ans = R - min
    if R < min:
        min = R
 
print ans

Submission status: Accepted

Solution code:
n = int( raw_input() )

min = 10 ** 10
ans = -10 ** 10


for i in xrange(n):
  x = int( raw_input() )
  if x - min > ans:
    ans = x - min
  if x < min:
    min = x

print ans

Submission status: Accepted

Solution code:
n = input()
n_max = -(10**9)
n_min = input() 
 
for i in range(0, n-1):
 R = input()
 if n_max < R - n_min:
  n_max = R - n_min
 if R < n_min:
  n_min = R
  
print n_max

Submission status: Accepted

Solution code:
n = input()
maxi = -1 * 10**9
mini = input()
 
 
for i in range(n-1):
  tmp = input()
  maxi = max(maxi, tmp - mini)
  mini = min(mini, tmp)
 
print maxi

Submission status: Accepted

Solution code:
n=input()
for i in range(n):
    if i==0:
        num_1=input()
    elif i==1:
        num_2=input()
        maxv=num_2 - num_1
        MIN=min(num_1,num_2)
    else:
        num_3=input()
        if (num_3-MIN)>maxv:
            maxv=num_3-MIN
        if (num_3)<MIN:
            MIN=num_3
print(maxv)

Submission status: Accepted

Solution code:
n = int(raw_input())
a = []
a.append(int(raw_input()))
Min = a[0]
Max = -1*10**9
for j in range(1,n):
    a.append(int(raw_input()))
    Max = max(Max,a[j]-Min)
    Min = min(Min,a[j])
print Max

Submission status: Accepted

Solution code:
#Reference : http://qiita.com/lethe2211/items/6cbade2bc547649bc040
#Reference : http://judge.u-aizu.ac.jp/onlinejudge/commentary.jsp?id=ALDS1_1_D
n = input()

R = []
for i in range(n):
    R.append(input())

min_v = R[0]
max_v = -pow(10, 9)
for i in range(1, n):
    temp = R[i] - min_v
    if (temp >= max_v):
        max_v = temp
    temp = R[i]
    if (min_v >= temp):
        min_v = temp
print max_v

Submission status: Accepted

Solution code:
n = input()
m = [0] * n
max_rieki = -1000000000



for i in xrange(n):
 m[i] = input()

min_rieki = m[0]
for i in xrange(1,n): 
  if max_rieki < m[i] - min_rieki:
     max_rieki = m[i] - min_rieki
  if min_rieki > m[i]:
     min_rieki = m[i]

print max_rieki

Submission status: Accepted

Solution code:
num = input()
l =[]

for i in range(num):
   l.append(int(raw_input()))

max = l[1] - l[0]
small = l[0]
for i in range(1, num):
   if small > l[i]:
      small = l[i]
   elif max < l[i] - small:
      max = l[i] - small
print max

Submission status: Accepted

Solution code:
n = input()

R = [input() for i in range(n)]
  
max = R[1] - R[0]
min = R[0]
  
for i in range(1,n):
    if R[i] - min > max:
        max = R[i] - min
    if R[i] < min:
        min = R[i]
  
print max

Submission status: Accepted

Solution code:
N=int(raw_input())
max=(-1)*(10**9)
x1=input()
min=x1

for i in range(N-1):
  x=int(raw_input())

  if max < x-min:
    max=x-min
  if min>x:
    min=x
print max

Submission status: Accepted

Solution code:
n = int(raw_input())
minv = int(raw_input())
maxv = -1*10**9  

for j in range(n-1):
    a = int(raw_input())
    b = a- minv
    if maxv < b:
       maxv = b 
    if minv > a:
       minv = a

print maxv

Submission status: Accepted

Solution code:
n = input()
minv = input()
maxv = -1 * 10**9

for j in range(n-1):
  v = input()
  if maxv < v - minv:
    maxv = v - minv
  if minv > v:
    minv = v

print maxv

Submission status: Accepted

Solution code:
maxv = -2*10**9
minv = 2*10**9
n = int(input())
for i in range(n):
    x = int(input())
    maxv = max(x-minv, maxv)
    minv = min(x, minv)
print maxv

Submission status: Accepted

Solution code:
n = int(input())
r_s = [int(input()) for i in range(n)]

minv = r_s[0]
maxv = r_s[1] - r_s[0]
for i in range(1, n):
    maxv = max(maxv, r_s[i]-minv)
    minv = min(minv, r_s[i])

print(maxv)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
def main():
    N = input() 
    a = [input() for y in range(N)] 
    a_max = -10**9
    a_min = a[0]
    for j in xrange(1,len(a)):
        if a[j] - a_min > a_max:
            a_max = a[j] - a_min
        if a[j] < a_min:
            a_min = a[j]
    print a_max
main()

Submission status: Accepted

Solution code:
max = -10 ** 9
n = int(input())
min = int(input())
for _ in range(n - 1):
    r = int(input())
    if max < (r - min):
        max = r - min
    if r < min:
        min = r
print(max)

Submission status: Accepted

Solution code:
def maximumProfit(A, N):
    minR = A[0]
    minP = A[1] - A[0]
    for i in range(1, N):
        R = A[i] - minR
        if R > minP:
            minP = R
        if A[i] < minR:
            minR = A[i]
    return minP

if __name__ == "__main__":
    N = input()
    A = []
    for i in range(N):
        A.append(input())
    print maximumProfit(A, N)

Submission status: Accepted

Solution code:
n = input()
R = [0 for i in range(n)]
for i in range(n):
    R[i] = input()
maxv = -2000000000
minv = R[0]

for j in range(1, n):
    maxv = max(maxv, R[j] - minv)
    minv = min(minv, R[j])

print maxv

Submission status: Accepted

Solution code:
N=int(input())
R=[int(input()) for x in range(N)]
maxv=-10**9
minv=R[0]
for r in R[1:]:
    maxv = max(r-minv,maxv)
    minv = min(r,minv)
print(maxv)

Submission status: Accepted

Solution code:
n = int(input())
data = [int(input()) for i in range(n)]

min_value = data.pop(0)
earn_value = -1000000000000
for d in data:
    earn_value = max(d - min_value, earn_value)
    min_value = min(d, min_value) 
print(earn_value)

Submission status: Accepted

Solution code:
n = input()

R = []
for i in range(n):
    R.append(input())

min_v = R[0]
max_v = -1000000000000
for i in range(1, n):
    temp = R[i] - min_v
    if (temp >= max_v):
        max_v = temp
    temp = R[i]
    if (min_v >= temp):
        min_v = temp
print max_v

Submission status: Accepted

Solution code:
n = input()

R = []
for i in range(n):
    R.append(input())

min_v = R[0]
max_v = -1000000000
for i in range(1, n):
    temp = R[i] - min_v
    if (temp >= max_v):
        max_v = temp
    temp = R[i]
    if (min_v >= temp):
        min_v = temp
print max_v

Submission status: Accepted

Solution code:
n = input()
R = []
for i in range(n):
    R.append(input())

maxv = R[1] - R[0]
minv = R[0]
for j in range(1, n):
    maxv = max(maxv, R[j] - minv)
    minv = min(minv, R[j])

print "%d" % maxv

Submission status: Accepted

Solution code:
#coding: UTF-8

N = int(input())

a = [int(input()) for i in range(N)]

ans = set()

maxv = -9999999999
minv = a[0]
for i in range(1,N):
    if (a[i] - minv) > maxv:
        maxv = a[i] - minv
    if a[i] < minv:
        minv = a[i]

print(maxv)

Submission status: Accepted

Solution code:
if __name__ == '__main__':
	n = int(input())
	R = [int(input()) for i in range(n)]

	minv = R[0]
	maxv = R[1] - R[0]
	for j in range(1, n):
		if (maxv < R[j] - minv):
			maxv = R[j] - minv
		if (R[j] < minv):
			minv = R[j]
	print(maxv)

Submission status: Accepted

Solution code:
n = int(raw_input())
R_list = [int(raw_input()) for _ in range(n)]

min_R = int(1e10)
ans = -int(1e10)
for R in R_list:
    ans = max(ans, R - min_R)
    min_R = min(min_R, R)

print ans

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

n = int(raw_input())
R_List = []
Max = 0
R_min = 0
for i in range(n):
    R_List.append(int(raw_input()))
    if i == 0:
        R_min = R_List[0]
    elif i == 1:
        Max = R_List[1]-R_min
        R_min = min(R_min, R_List[1])
    else:
        Max = max(Max, R_List[i]-R_min)
        R_min = min(R_min, R_List[i])
print Max

Submission status: Accepted

Solution code:
import math
A = []
N = int(input())
maxdiff = 0
for n in range(N):
    A.append(int(input()))
R = tuple(A)

Dmax = R[1] -R[0]
Rmin = R[0]

for i in range(1, N):
    if R[i] >= R[i-1]:
        if R[i] - Rmin > Dmax:
            Dmax = R[i] -Rmin
    if R[i] < Rmin:
        Rmin = R[i]
#    print(R[i], Dmax, Rmin)

print(Dmax)

Submission status: Accepted

Solution code:
dif = -1E9
n = int(input())
mn = int(input())
for i in range(n - 1):
    r = int(input())
    if r - mn > dif:
        dif = r - mn
    if r < mn:
        mn = r
print(dif)

Submission status: Accepted

Solution code:
n = input()
minv = input()
maxv = -2000000000 #10**9-10**9
for i in xrange(1, n):
    r = input()
    maxv = max(maxv, r - minv)
    minv = min(minv, r)

print maxv

Submission status: Accepted

Solution code:
#cording by utf-8

n = int(input())
#maxv ?????§???
#minv ????°????
minv = int(input()) #?????????????°????
#print("minv",minv)
maxp = int(input()) #??????????????§???
maxp = maxp - minv
if maxp + minv < minv:
    minv = maxp + minv
for i in range(2,n):
    stock = int(input())
    if minv > stock:
        minv = stock
        #print("minv",minv)
    else:
        profit = stock - minv
        if profit > maxp:
            maxp = profit
            #print("maxp",maxp)

print(maxp)

Submission status: Accepted

Solution code:
import sys

line_num = int(sys.stdin.readline().rstrip())
maxv = -2000000000
minv = int(sys.stdin.readline().rstrip())

for i in range(1, line_num):
    rt = int(sys.stdin.readline())
    if rt - minv > maxv:
        maxv = rt - minv
    if rt < minv:
        minv = rt

print(maxv)

Submission status: Accepted

Solution code:
input_n = input()
price1  = input()
price2  = input()
min_price = min(price1,price2)
max_profit = price2-price1
for i in xrange(input_n-2):
    input_profit = input()
    tmp = input_profit-min_price
    if max_profit<tmp:
        max_profit = tmp
    if min_price>input_profit:
        min_price = input_profit
print max_profit

Submission status: Accepted

Solution code:
from itertools import islice


def maximum_profit(rate):
    ret = -float("inf")
    mi = rate[0]
    for r in islice(rate, 1, len(rate)):
        ret = max(ret, r - mi)
        mi = min(mi, r)
    return ret

if __name__ == "__main__":
    R = [int(input()) for _ in range(int(input()))]
    print(maximum_profit(R))

Submission status: Accepted

Solution code:
from functools import reduce


def maximum_profit(profit_minrate, rate):
    profit, minrate = profit_minrate
    return max(profit, rate-minrate), min(minrate, rate)

if __name__ == "__main__":
    R = [int(input()) for _ in range(int(input()))]
    print(reduce(maximum_profit, R, (-float("inf"), float("inf")))[0])

Submission status: Accepted

Solution code:
def maximum_profit(profit_minrate, rate):
    profit, minrate = profit_minrate
    return max(profit, rate-minrate), min(minrate, rate)

if __name__ == "__main__":
    R = [input() for _ in range(input())]
    print reduce(maximum_profit, R, (-float("inf"), float("inf")))[0]

Submission status: Accepted

Solution code:
N=input()
input = [int(input()) for i in range(int(N))]
maxv=-10000000000
minv=10000000000
for i,x in enumerate(input):
	maxv = max(maxv, input[i]-minv)
	minv = min(minv, input[i])
print(maxv)

Submission status: Accepted

Solution code:
n = input()
R = [input() for i in xrange(n)]

Rmin = n
maxdif = R[1] - R[0]

while Rmin > 0:
    tRmin = R.index(min(R[0:Rmin]))
    Rmax = R.index(max(R[tRmin:Rmin]))
    if tRmin == Rmax:
        if tRmin == n-1:
            tRmin-=1
        elif tRmin < n-1:
            Rmax = tRmin + 1
    Rmin = tRmin
    if (R[Rmax] - R[Rmin]) > maxdif:
        maxdif = R[Rmax] - R[Rmin]

print maxdif

Submission status: Accepted

Solution code:
#coding: utf-8
#ALDS1_1D
import sys

n=int(raw_input())
minv=float("inf")
maxv=float("-inf")
for i in xrange(1,n+1):
 r=int(raw_input())
 maxv=max(maxv,r-minv)
 minv=min(minv,r)

print maxv

Submission status: Accepted

Solution code:
n = int(input())
r_min = int(input())
r_t   = int(input())
g_max = r_t - r_min
r_min = min(r_t,r_min)
for _ in range(n-2):
    r_t = int(input())
    g_max = max(g_max, r_t-r_min)
    r_min = min(r_t,r_min)
print(g_max)

Submission status: Accepted

Solution code:
n = int(input())
values = [int(input()) for i in range(n)]

maxv = -999999999
minimum = values[0]

for i in range(1, n):
    if values[i] - minimum > maxv:
        maxv = values[i] - minimum
    if values[i] < minimum:
        minimum = values[i]

print(maxv)

Submission status: Accepted

Solution code:
n = input()
Max = -4300000000
Min = input()
for i in range(n - 1):
    IN_NOW = input()

    Max = max(Max, (IN_NOW - Min))    
    Min = min(Min, IN_NOW)
    
print Max

Submission status: Accepted

Solution code:
n = int(input())
arr = [int(input()) for i in range(n)]

m = 1 - 10**9
minv = arr[0]
for i in range(1,len(arr)):
    if arr[i] - minv > m:
        m = arr[i] - minv
    minv = min(minv, arr[i])
print(m)

Submission status: Accepted

Solution code:
import math

n = int(input())
minv = int(input())
maxv = -math.pow(10, 9)

for _ in range(n-1):
    rt = int(input())
    maxv = max(maxv, rt - minv)
    minv = min(minv, rt)

print(maxv)

Submission status: Accepted

Solution code:
import sys

n = int(input())
r0 = int(input())
r1 = int(input())

mx = r1-r0
mn = min(r1,r0)
l = map(int,sys.stdin.readlines())
for i in l:
    if mx < i - mn:
        mx = i - mn
    elif mn > i:
        mn = i

print(mx)

Submission status: Accepted

Solution code:
import sys

n = int(input())
r0 = int(input())
r1 = int(input())
mx = r1-r0
mn = min(r1,r0)

for i in map(int,sys.stdin.readlines()):
    if mx < i - mn:
        mx = i - mn
    elif mn > i:
        mn = i

print(mx)

Submission status: Accepted

Solution code:
num = int(input())
min = int(input())
diff = -2000000000

for var in range(1,num):
    data = int(input())
    current = data - min
    if current > diff :
        diff = current
    if min > data :
        min = data

print(diff)

Submission status: Accepted

Solution code:
import sys
 
n = int(input())
r0 = int(input())
r1 = int(input())
mx = r1-r0
mn = min(r1,r0)
 
for i in map(int,sys.stdin.readlines()):
    if mx < i - mn:
        mx = i - mn
    if mn > i:
        mn = i
 
print(mx)

Submission status: Accepted

Solution code:
import sys

n = int(input())
r0 = int(input())
r1 = int(input())
mx = r1-r0
mn = min(r1,r0)

for i in map(int,sys.stdin.readlines()):
    if mx < i - mn:
        mx = i - mn
        if 0 > i-mn:
            mn = i
    elif mn > i:
        mn = i

print(mx)

Submission status: Accepted

Solution code:
# http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_1_D
sample_input = '''
3
4
3
2
'''
give_sample_input = False
if give_sample_input:
  sample_input_list = sample_input.split()
  def input():
    return sample_input_list.pop(0)

numOfData = int(input())
max_diff = None  # minus infty
min_val = None  # plus infty
prev_val = int(input())
for n in range(numOfData-1):
	val = int(input())
	if min_val is None:
		min_val = prev_val
	else:
		min_val = min(prev_val, min_val)
	if max_diff is None:
	  max_diff = val - min_val
	else:
	  max_diff = max(val - min_val, max_diff)
	prev_val = val

print(max_diff)

Submission status: Accepted

Solution code:
n = int(input())
r = []
for i in range(n):
    r.append(int(input()))

min = r[0]
max = -10 ** 12

for j in r[1:]:
    if j - min > max:
        max = j - min
    if min > j:
        min = j

print(max)

Submission status: Accepted

Solution code:
#!/usr/bin/python


def main():
  times = int(input())
  min_rate = int(input())
  maxv = - 10 ** 9
  for _ in range(1, times):
    rate = int(input())

    if rate - min_rate > maxv:
      maxv = rate - min_rate

    if rate < min_rate:
      min_rate = rate

  print(maxv)
  return 0


if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
N = input()
R = [input() for i in range(N)]

min_v = float("inf")
ans = -float("inf")
for r in R:
    ans = max(ans, r - min_v)
    min_v = min(min_v, r)
    
print ans

Submission status: Accepted

Solution code:
n = int(input())
R = [int(input()) for i in range(n)]
maxv = R[1] - R[0]
minv = R[0]

for j in range(1, n):
    maxv = R[j] - minv if R[j] - minv > maxv else maxv
    minv = R[j] if R[j] < minv else minv

print(maxv)

Submission status: Accepted

Solution code:
def getsub(arr):
    minv = arr[0]
    maxdist = arr[1] - minv

    for v in arr[1:]:
        # update maxdist
        maxdist = max(maxdist, v- minv)

        # update minv
        minv = min(minv, v)

    return maxdist

def main():
    # get input
    N = int(input())
    arr = [int(input()) for i in range(N)]

    # get sub
    print(getsub(arr))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
r = [int(input()) for x in range(n)]
maxv = -2000000000
minv = r[0]

for i in range(1, n):
    maxv = max(maxv, r[i] - minv)
    minv = min(minv, r[i])

print(maxv)

Submission status: Accepted

Solution code:
# coding: utf-8

n = int(input())

max_val = -10 ** 10
min_val = int(input())

for i in range(n - 1):
    t = int(input())
    max_val = max(max_val, t - min_val)
    min_val = min(min_val, t)

print(max_val)

Submission status: Accepted

Solution code:
num = int(input())
minnum = 10 ** 18 + 1
ans = (-10 ** 9 - 1)
for n in range(num):
    newnum = int(input())
    ans = max(ans,newnum - minnum)
    minnum = min(minnum,newnum)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
a = []
for i in range(N):
    a.append(int(input()))
max_profit = a[1] - a[0]
min_val = min(a[1],a[0])
for i in range(2,N):
	if a[i] < min_val:
		min_val = a[i]
	elif a[i] - min_val > max_profit:
		max_profit = a[i] - min_val
print(str(max_profit))

Submission status: Accepted

Solution code:
N = int(input())
r = [int(input()) for i in range(N)]
 
min = r[0]
max = -9999999999999999
 
for i in range(1, N):
    if r[i] - min > max:
        max = r[i] - min
    if r[i] < min:
        min = r[i]
 
print(max)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
from __future__ import (absolute_import, division,
                                print_function, unicode_literals)
import sys

n = int(input())
r = []
for i in range(n):
    r.append(int(input()))

c = sys.maxsize
ret = -sys.maxsize - 1
for j in range(n):
    ret = max([ret, r[j] - c])
    if(r[j] < c):
        c = r[j]

print(ret)

Submission status: Accepted

Solution code:
n = int(input())
ps = [int(input()) for _ in range(n)]
maxpro = -999999999
minp = 1000000000
for i, p in enumerate(ps[:-1]):
  if p >= minp: continue
  pro = max(ps[i + 1:]) - p
  maxpro = max(pro, maxpro)
  minp = p
print(maxpro)

Submission status: Accepted

Solution code:
n = int(input())
nums = [int(input()) for i in range(n)]
temp = nums[1] - nums[0]
p = nums[0]

for i in nums[1:]:
    if i - p > temp:
        temp = i- p
    if i < p:
        p = i
print(temp)

Submission status: Accepted

Solution code:
import sys,math

n=0
max_v=-math.pow(10,10)
s=math.pow(10,10)
for line in sys.stdin:
    l=int(line)
    if n == 0:
        n=l
        continue
    diff=l-s
    if diff>max_v:
        max_v=diff
    if diff<0:
        s=l
        

print max_v

Submission status: Accepted

Solution code:
# -*- coding:utf-8 -*-

num = int(input())
min = 0
sa = -10000000000
for i in range(num):
    atai = int(input())
    if i == 0:
        min = atai
        continue
    sa_temp = atai - min
    if sa < sa_temp:
        sa = sa_temp
    if min > atai:
        min = atai
print(sa)

Submission status: Accepted

Solution code:
n=int(input())
x0=int(input())
ma=-1111111111
mi=x0
for _ in range(n-1):
    x=int(input())
    if ma<x-mi:
        ma=x-mi
    if mi>x:
        mi=x
print(ma)

Submission status: Accepted

Solution code:
n = int(input())

r = -10000000000
y = int(input())

m = y
x = y

for i in range(1, n):
    x = int(input())
    if r < (x - m):
        r = (x - m)

    if x < m:
        m = x

print(r)

Submission status: Accepted

Solution code:
import sys


def read_data():
    r_data = []
    n = int(sys.stdin.readline().strip())
    
    for _ in range(n):
        r = int(sys.stdin.readline().strip())
        r_data.append(r)

    return n, r_data
    
def main():
    n, r_data = read_data()
    maxv = -1000000000
    minv = r_data[0]
    
    for j in range(1, n):
        if r_data[j] - minv > maxv:
            maxv = r_data[j] - minv

        if r_data[j] < minv:
            minv = r_data[j]

    print(maxv)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(raw_input())
maxprofit = -2 * 10 ** 9
minval = int(raw_input())
for _ in xrange(n-1):
  R = int(raw_input())
  maxprofit = max(maxprofit, R-minval)
  minval = min(minval, R)
print maxprofit

Submission status: Accepted

Solution code:
_temp = []

size = int(input().rstrip())
for i in range(size):
    try:
        _temp.append(int(input()))
    except EOFError:
        continue

my_max = -20000000000000
my_min = _temp.pop(0)


for val in _temp:
    my_max = max(my_max, (val - my_min))
    my_min = min(my_min, val)

print(my_max)

Submission status: Accepted

Solution code:
a=input()
r=[]
for i in range(a):
    k=input()
    r.append(k)
minv=r[0]
maxv=-10**9
for j in range(1,len(r)):
    maxv=max(maxv,r[j]-minv)
    minv=min(minv,r[j])
print maxv

Submission status: Accepted

Solution code:
import sys
INF = (sys.maxint)/3

def MaximumProfit(R_list):
	minR = INF
	maxD = -INF
	for R in R_list:
		maxD = max(maxD, R - minR)
		minR = min(minR, R)
	return maxD

def main():
	n = input()
	R_list = []
	for i in range(n):
		R_list.append(input())
	print MaximumProfit(R_list)

if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
m = int(input())
n = [int(input())for i in range(m)]

minv = n[0]
maxv = -99999999999

for i in range(1,m):
    maxv = max(maxv, (n[i]-minv))
    minv = min(minv, n[i])

print(maxv)

Submission status: Accepted

Solution code:
#coding:UTF-8

def MP(n,a):
    minv=a[0]
    maxv=a[1]-a[0]
    for i in range(1,n):
        if maxv<a[i]-minv:
            maxv=a[i]-minv
        if minv>a[i]:
            minv=a[i]    
    print(maxv)
if __name__=="__main__":
    n=int(input())
    a=[]
    for i in range(n):
        a.append(int(input()))
    MP(n,a)

Submission status: Accepted

Solution code:
n=input()
min = None
max = None
cand=None

for x in xrange(n):
    v = input()
   
    # print "#### %s %s %s %s" % (str(max), str(min), str(cand), str(v))

    if min is None:
        min = v
        # print "min is None"
        continue

    if min > v:
        # print "min > v"
        if (cand is None) or (cand < v-min):
            # print "cand None"
            cand = v-min
        min = v
        max = None
        continue

    elif (max is None) or (max < v):
        # print "max is None"
        max = v
        if cand < max - min:
            cand = max - min
        continue

print cand

Submission status: Accepted

Solution code:
n=input()
min = input()
profit = None

for x in xrange(n-1):
    v = input()
    if profit is None:
        profit = v - min
    if profit < v - min:
        profit = v-min
    if min > v:
        min = v
print profit

Submission status: Accepted

Solution code:
n = int(input())
R = []
for i in range(n):
    R.append(int(input()))

# R???i???????????§???????°???????i?????????????´???¨???????????????list
mins = [R[0]]
for i in range(1, n):
    mins.append(min(R[i], mins[i-1]))

# ???????????????j????????????????????\??????????°??????¨??????????±?????????????????????§???????±????????????????
mx = - 10 ** 12
for j in range(1, n):
    mx = max(mx, R[j] - mins[j-1])

print(mx)

Submission status: Accepted

Solution code:
n = int(input())

# R[0]
minv = int(input())
maxv = - 10 ** 10

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

print(maxv)

Submission status: Accepted

Solution code:
N = int(raw_input())
nums = []

for i in range(N):
    nums.append(int(raw_input()))

m = -1000000000000000000000000
minvalue = nums[0]

for i in range(1, len(nums)):
    minvalue = min(minvalue, nums[i-1])
    value = nums[i] - minvalue
    if m <= value:
        m = value

print(m)

Submission status: Accepted

Solution code:
n = int(input())
a = int(input())
b = int(input())

interest = b - a
min = min(a,b)
for i in range(n-2):
    f = int(input())
    if f - min > interest:
        interest = f - min
    elif f < min:
        min = f
print(interest)

Submission status: Accepted

Solution code:

def search_maximum_profit(rs):
    """
        rs: ??´??°?????????
        search max[s | s = rs[j] - rs[i] (j > i)]
        return: s
    """
    l = len(rs)
    if l <= 1:
        return None
    elif l == 2:
        return rs[1] - rs[0]
    else:
        left_profit = search_maximum_profit(rs[:l // 2])
        right_profit = search_maximum_profit(rs[l // 2:])
        left_min = min(rs[:l // 2])
        right_max = max(rs[l // 2:])
        profits = []
        if left_profit != None:
            profits.append(left_profit)
        if right_profit != None:
            profits.append(right_profit)
        profits.append(right_max - left_min)
        return max(profits)

n = int(input())
rs = []
for i in range(n):
    rs.append(int(input()))

print(search_maximum_profit(rs))

Submission status: Accepted

Solution code:
#!/usr/bin/env python
#-*- coding:utf-8 -*-

N = int(raw_input())

R = [int(raw_input()) for _ in range(N)]

minR = R[0]
maxVal = -2000000000

for i in R[1::]:
    maxVal = max(maxVal,i - minR)
    minR = min(minR, i)

print maxVal

Submission status: Accepted

Solution code:
n = int(input())
p = -10 ** 10
rmin= 10 ** 10
while n > 0:
    r = int(input())
    if n == 0:
        rmax = r
    else:
        if r - rmin > p:
            p = r - rmin
        if r < rmin:
            rmin = r
    n -= 1
print(p)

Submission status: Accepted

Solution code:
N = input()
nums = []
for i in range(N):
     nums.append(input())
profit = nums[1] - nums[0]
min = nums[0]
for a in range(1, N):
     if nums[a] - min > profit:
          profit = nums[a] - min

     if nums[a] < min:
               min = nums[a]
print profit

Submission status: Accepted

Solution code:
N = input()
R = [int(raw_input()) for _ in xrange(N)]
S = [0 for i in xrange(N)]
S[N-1] = R[N-1]
for i in xrange(N-2, -1, -1):
    S[i] = max(R[i], S[i+1])
ans = float('-inf')
for i in xrange(N-1):
    ans = max(ans, S[i+1]-R[i])
print ans

Submission status: Accepted

Solution code:
#http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_1_D
#?????§??????
#??????????????????????????°???????????????????????¢?????´?????????????????????
def get_maximum_profit(value_list, n_list):
    minv = pow(10,10) + 1
    profit = -minv
    for v in value_list:
        profit = max(profit, v - minv) 
        minv = min(minv, v)
    return profit

def main():
    n_list = int(input())
    target_list = [int(input()) for i in range(n_list)]
    print(get_maximum_profit(target_list, n_list))
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

def solve():
    n = int(raw_input())
    R = []

    for i in xrange(n):
        R.append(int(raw_input()))

    #for i in xrange(n):
    #    print R[i]

    max_profit = -sys.maxint
    min_R = R[0]

    for i in xrange(1, n):
        if R[i] - min_R > max_profit:
            max_profit = R[i] - min_R
        if min_R > R[i]:
            min_R = R[i]

    print max_profit


if __name__ == "__main__":
    solve()