A python code not work in array

Good work! Although there could be a few improvements made to the code but let's focus on the one bug that causes it to return the wrong result:

    Max = max(Max, prices[j] - prices[i])
    j+=1
j+=1

It's the double j += 1. Whenever the maximum is changed j is incremented twice, skipping some comparisons.

Remove the j += 1 inside the if-branch and you get the correct result for the input vector:

    Max = max(Max, prices[j] - prices[i])
j+=1

If interested, here are a few tips to improve coding style:

• while i+1 <= len(prices)-1: adding 1 and using <= is redundant. while i < len(prices)-1: would be slightly cleaner.

• For loops are easier to read than while loops and have slightly better performance. Use them when there is only one counter to be increased:

  for i in range(len(prices)):
      for j in range(i, len(prices)):
          if prices[i] < prices[j]:
              Max = max(Max, prices[j] - prices[i])
  

• No need to use a class in this case.

class Solution(object):
def maxProfit(self, prices):
    """
    :type prices: List[int]
    :rtype: int
    """
    i=Max=0
    if not prices:
        return 0
    while i+1 <= len(prices)-1:
        j=i+1
        while j < len(prices):
            if prices[i] < prices[j]:
                Max = max(Max, prices[j] - prices[i])
                j+=1 // <---THIS IS BUGGY LINE
            j+=1
        i+=1
    return Max

If the buggy line executes, j will += 2 in total, which may skip some value in the array to be price[j].

In your case, when i = 0, j = 1, you will get Max = price[1] - price[0] = 1.

Then j will += 2 which is out of bound, so you never get Max = price[2] - price[0] = 3.

Then when i = 1, j = 2, you will get Max = price[2] - price[1] = 2 which is your final result

From what I understand, I believe you have to rephrase and adjust the problem into code. My observations based on the examples and expected results:

• The buying price is in the input list and has to be identified
• The selling price is also in the input list and has to be identified
• The buying price must be less than selling price
• The profit is the output and thus is buying-selling

Now, converting this to an algorithm:

Attempt 1 (wrong in some cases - see comments)

1. Find the minimum in the list - this is our buying price
2. Find the maximum in the list that is on the "same or later day" ie. the index is the same or larger than the buying price index

The code (single executable - you need to make it a function if needed):

#!/usr/bin/env python

import sys

# Not part of the algorithm: converts first argument to a list of integers
prices = map(int, sys.argv[1].split(","))

# Find the best buying price
buy = min(prices)
# Find the best buying time/index
buyidx = prices.index(buy)

# Now the best selling price is the next maximum
sell = max(prices[buyidx:])

print(" Input: %s" % str(prices))
print("Output: %d" % (sell-buy))

Examples:

$ /tmp/stock.py 1,2,4
 Input: [1, 2, 4]
Output: 3
$ /tmp/stock.py 7,1,5,3,6,4
 Input: [7, 1, 5, 3, 6, 4]
Output: 5

$ /tmp/stock.py 1,2,3,4,5
 Input: [1, 2, 3, 4, 5]
Output: 4
$ /tmp/stock.py 4,3,2
 Input: [4, 3, 2]
Output: 0
$ /tmp/stock.py 4,3,1
 Input: [4, 3, 1]
Output: 0
$ /tmp/stock.py 4,3,5
 Input: [4, 3, 5]
Output: 2

Attempt 2 based on @kazemakase input

1. The buying price is in the list but is not necessarily the minimum value. It is the value that maximizes the profit!
2. For every day, calculate what our profit would be if we buy the stock that day - The selling price is the max value with index greater than the current day
3. (@kazemakase) Loops are sometimes inevitable

The code:

#!/usr/bin/env python

import sys

prices = map(int, sys.argv[1].split(","))

# For every day
buy_final = 0
sell_final = 0
max_profit = 0
for (buyindex, buy) in enumerate(prices):
    sell = max(prices[buyindex:])
    profit = sell - buy
    if profit > max_profit:
        max_profit = profit
        buy_final = buy
        sell_final = sell

print(" Input: %s" % str(prices))
print("Output: %d" % (sell_final-buy_final))

The results:

$ /tmp/stock.py 7,1,5,3,6,4
 Input: [7, 1, 5, 3, 6, 4]
Output: 5
$ /tmp/stock.py 1,2,4
 Input: [1, 2, 4]
Output: 3
$ /tmp/stock.py 3,6,1,2
 Input: [3, 6, 1, 2]
Output: 3

Let me know if you need more clarification, or if my assumptions are wrong

You one j incrementation is not necessary.

def maxProfit(self, prices):
    """
    :type prices: List[int]
    :rtype: int
    """
    i=Max=0
    if not prices:
        return 0
    while i+1 <= len(prices)-1:
        j=i+1
        while j < len(prices):
            if prices[i] < prices[j]:
                Max = max(Max, prices[j] - prices[i])
            j+=1
        i+=1
    return Max

But I propose more simple solution. My idea for this task is to loop over prices and try each time if I buy at given price I am able to sell it in more expensive.

def max_profit(prices):
  profit = 0
  for i in range(len(prices)):
    buy_price = prices[i]
    max_sell_price = max(prices[i:])
    diff = max_sell_price - buy_price
    if diff > profit:
      profit = diff
  return profit

print(max_profit([7, 1, 5, 3, 6, 4]))
print(max_profit([7, 6, 4, 3, 1]))
print(max_profit([1, 2, 4]))

Output:

5
0
3

As we traverse the price list, let's consider each value after the first as a potential selling price. What would be the ideal buying price?

Hints: we've already seen it and it can be updated as we go along in O(1) time and space (a benefit we don't normally have in the real world :).