Finding maximum difference between consecutive elements of an array

Question

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]

Why are you focused on consecutive days, since the optimal answer can be across several days? — BrokenBenchmark
– BrokenBenchmark, Commented Mar 3, 2022 at 16:49
@dawg, I'd be surprised if this question had not been asked before but it is not the same as the question you cite that serves as the basis for closing. This question is concerned with successive elements, not any pair of elements. — Cary Swoveland
– Cary Swoveland, Commented Mar 3, 2022 at 17:30
max(((t1-e1,(e1,t1)) for i,e1 in enumerate(your_list) for t1 in li[i+1:])) — dawg
– dawg, Commented Mar 3, 2022 at 18:48

Ekesh Kumar · Accepted Answer · 2022-03-04 03:12:11Z

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.

answered Mar 4, 2022 at 3:12

Ekesh Kumar

5254 silver badges12 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

holmrenser Over a year ago

OP asks for python, which this is not.

Madhan S · Accepted Answer · 2022-03-03 17:03:25Z

0

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

answered Mar 3, 2022 at 17:03

Madhan S

6931 gold badge6 silver badges17 bronze badges

Comments

jjail · Accepted Answer · 2022-04-24 22:01:40Z

0

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

answered Apr 24, 2022 at 22:01

jjail

11 bronze badge

1 Comment

Community Over a year ago

Your answer could be improved with additional supporting information. Please edit to add further details, such as citations or documentation, so that others can confirm that your answer is correct. You can find more information on how to write good answers in the help center.

Collectives™ on Stack Overflow

Finding maximum difference between consecutive elements of an array

3 Answers 3

1 Comment

Comments

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related