A python code not work in array

Question

It is an algorithm question whose topic is : Best Time to Buy and Sell Stock

Say you have an array for which the ith element is the price of a given stock on day i. If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

*Example 1: Input: [7, 1, 5, 3, 6, 4] Output: 5

max. difference = 6-1 = 5 (not 7-1 = 6, as selling price needs to be larger than buying price).*

*Example 2: Input: [7, 6, 4, 3, 1] Output: 0

In this case, no transaction is done, i.e. max profit = 0.*

I worked it out using python. Codes are as follows:

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
            j+=1
        i+=1
    return Max

However, the system returned me that I was wrong: Return wrong

Tried but I can't figure out where the error is... Can someone help please ? Thanks a lot!

Answer 1

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.

Answer 2

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