'Finding maximum difference between consecutive elements of an array

Say I have an array:

[44, 30, 24, 32, 35, 30, 40, 38, 15]

Here, every number represents a stock value on a certain day. I want to find the maximum profit that could have been made by buying stock on day x and selling stock on day y.

In this case, the function would return 16, because at index 2 the stock was worth $24 and at index 6 the stock was then worth $40.

Here is my attempt, however I can't figure out how to only look at consecutive elements in the list

x = [5, 8, 15, 19]  # total scores
y = [x[i] - x[i-1] if i else x[i] for i in range(len(x))]  # round scores
print(y)
# output
[5, 3, 7, 4]
pythonlistalgorithm


Solution 1:[1]

Once you pass index i, it's never optimal to buy the stock at any value other than min_{1 <= j <= i} A[j], so it's enough to compare the minimum value so far to the present value.

int solve(stock_prices) { 
  int answer = 0, min_so_far = stock_prices[0];
  for (int i = 1; i < n; ++i) {
    answer = max(answer, stock_prices[i] - min_so_far);
    min_so_far = min(min_so_far, stock_prices[i]);
  }
  return answer;
}

This runs in linear time compared to the other two solutions, both of which are quadratic.

Solution 2:[2]

You can look at consecutive elements this way.

...
for i in range(len(x):
    for j in range(i+1, len(x)):
...

Here is the working one:

def max_difference(price_list):
  days = len(price_list)
  max_diff=0
  for i in range(days-1):
    for j in range(i+1, days):
      diff = price_list[j]-price_list[i]
      if(diff > max_diff):
        max_diff=diff
  return max_diff

prices=[10, 30, 40, 32, 35, 30, 40, 38, 15]
print(max_difference(prices))

Solution 3:[3]

This is Ekesh Kumar's answer but converted to Python, and it will also return 0 if there is no positive profit to be made (monotonically decreasing list):

#Set initial profit to zero
max_profit = 0
#Grab our first purchase value
min_price_so_far = prices[0]

#Start at 1 so we can compare to the first day price
for i in range(1,len(prices)):
    max_profit = max(max_profit, prices[i] - min_price_so_far)
    min_price_so_far = min(min_price_so_far, prices[i])
    
print(max(max_profit, 0))

Sources

This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.

Source: Stack Overflow

Solution Source
Solution 1 Ekesh Kumar
Solution 2 Madhan S
Solution 3 jjail

Related Questions