Finding maximum difference between consecutive elements of an array-CodePudding

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]

CodePudding user response：

You could construct a dictionary and then use max. The idea is to find the max returns for each item (stored as values) and find the index of the value that has the highest returns:

tmp = {idx: max(j-i for j in lst[idx:]) for idx, i in enumerate(lst)}
out = max(tmp, key = tmp.get)

Output:

If you just want the highest return, we don't even need a dictionary:

out = max(max(j-i for j in lst[idx:]) for idx, i in enumerate(lst))

Output:

CodePudding user response：

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))

CodePudding user response：

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.