"""

MaxProfit
START
Given a log of stock prices compute the maximum possible earning.
Programming language:  Spoken language:
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].
"""

import random


# worst case
def solution2(A):
    n = len(A)
    darr = [[0] * n] * n
    for i in range(n):
        for j in range(i):
            darr[i][j] = A[i] - A[j]
    # print(np.array(darr[n-1]))
    max_profit = max(darr[n - 1])
    return max_profit


def solution2(A):
    days = len(A)
    if days < 2:
        return 0
    max_price_from_here = A[days - 1]
    max_profit = 0
    for i in range(days - 2, -1, -1):
        max_profit = max(max_profit, max_price_from_here - A[i])
        max_price_from_here = max(A[i], max_price_from_here)
    return max_profit


def solution(A):
    n = len(A)
    max_profit = 0
    min_val = 0
    for i in range(n):
        item = A[i]
        if min_val == 0 or item < min_val:
            min_val = item
        elif max_profit == 0 or (item - min_val) > max_profit:
            max_profit = item - min_val
    return max_profit


# A = [round(random.random()*10000) for i in range(500000)]
A = [23171, 21011, 21123, 21366, 21013, 21367]
# print("max profit possible is",A)
print(solution(A))
