Codility 9.1 MaxProfit [Maximum

Given a log of stock prices compute the maximum possible earning.

Task description
An array A consisting of N integers is given. It contains daily prices of a stock share for a period of N consecutive days. If a single share was bought on day P and sold on day Q, where 0 ≤ P ≤ Q < N, then the profit of such transaction is equal to A[Q] − A[P], provided that A[Q] ≥ A[P]. Otherwise, the transaction brings loss of A[P] − A[Q].

For example, consider the following array A consisting of six elements such that:

  A[0] = 23171
  A[1] = 21011
  A[2] = 21123
  A[3] = 21366
  A[4] = 21013
  A[5] = 21367
If a share was bought on day 0 and sold on day 2, a loss of 2048 would occur because A[2] − A[0] = 21123 − 23171 = −2048. If a share was bought on day 4 and sold on day 5, a profit of 354 would occur because A[5] − A[4] = 21367 − 21013 = 354. Maximum possible profit was 356. It would occur if a share was bought on day 1 and sold on day 5.

Write a function,

def solution(A)

that, given an array A consisting of N integers containing daily prices of a stock share for a period of N consecutive days, returns the maximum possible profit from one transaction during this period. The function should return 0 if it was impossible to gain any profit.

For example, given array A consisting of six elements such that:

  A[0] = 23171
  A[1] = 21011
  A[2] = 21123
  A[3] = 21366
  A[4] = 21013
  A[5] = 21367
the function should return 356, as explained above.

Write an efficient algorithm for the following assumptions:

N is an integer within the range [0..400,000];
each element of array A is an integer within the range [0..200,000].

思路：这道题的原型是 slice maximum problem，我们计算到每个位置的最大和。
假设在第i元素有最大的和max_ending。那么在i+1时，最大的和= max{0, max_ending+a_{i+1}}。max_slice存储最大值。

def golden_max_slice(A):
      max_ending = max_slice = 0
      for a in A:
          max_ending = max(0, max_ending + a)
          max_slice = max(max_slice, max_ending)
     return max_slice

这道题求最大利润。同样的，我们计算从每个位置起的最大差。假设在第i个元素有最大差，也就是第i个元素是最小值min_start，那么，在i+1时，最小值为min(i+1,min_start) 。max_slice存储最大利润。

#O（N）
def solution(A):
    # write your code in Python 3.6
    if len(A) ==0:
        return 0
    min_start = A[0]
    max_slice = 0
    #在position i买进，也就是i 是min
    for i in A:
        min_start = min(i,min_start)    
        max_slice = max(i-min_start,max_slice)
    if max_slice>0:
        return max_slice
    else:
        return 0