CODEWITHSUNDEEP
python
user
user

Reputation: 234

Algorithm to find the maximum profit

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 (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Note that you cannot sell a stock before you buy one.

Input: [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
             Not 7-1 = 6, as selling price needs to be larger than buying price.

Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

Here is my algorithm. It works fine with the first and fourth arrays, but for some reason i'm not sure why it's not working for the 3rd array:

def maxProfit(prices):
    dif=[]
    current_min=[]
    for i in range(len(prices)):
        for k in range(1,len(prices)):
            dif.append(prices[i]-prices[k])
            if prices[i]-prices[k]==min(dif):
                if i<k:
                    current_min.append([i,k])
    print("current indices of price array where profit is maximum:" +str(current_min))
    
    res=prices[current_min[-1][1]]-prices[current_min[-1][0]]
    if res<0:
        return str(0) + "\n"
    elif res>=0:
        return "Max profit is " +str(res) + "\n"
    
    
                
print(maxProfit([7,1,5,3,6,4]))
print(maxProfit([7,6,4,3,1]))
print(maxProfit([3,3,5,0,0,3,1,4]))
print(maxProfit([3,3,0,3,1,4]))

Output:

current indices of price array where profit is maximum:[[0, 1], [0, 2], [0, 4], [1, 2], [1, 4]]
Max profit is 5

current indices of price array where profit is maximum:[[0, 1]]
0

current indices of price array where profit is maximum:[[0, 1], [0, 2], [1, 2]]
Max profit is 2

current indices of price array where profit is maximum:[[0, 1], [0, 3], [0, 5], [1, 5], [2, 3], [2, 5]]
Max profit is 4

For the third array, for some reason the for loops stops iterating at i=1. Why is this so?

PS. My algo is maybe not the most efficient, but i'm just trying to understand why my solution is not working with that specific array. I am not interested in an alternative method of solving this problem, as I have seen loads of them.

Upvotes: 1

Views: 4867

Answers (3)

Aastha Sethia
Aastha Sethia

Reputation: 39

Your Algorithm stops working because after reaching the index 2, which is 5 current_minimum is not appended as 5-0 =5 which is not the minimum of diff (which comes out at -2 later -3 you can see in the dry run or debugging)array hence appending in current_min does not happen, debug your code add pointers at diff_min and current_min you will be able to see the whole flow, you also need to add a check for is the trade valid or not

The array is the prices of stock on the given day, basically: Stock_1 = {100, 180, 260, 310, 40, 535, 695} so the best way to maximize profit would be to buy on day 0 sell on day 3 then buy on day 4 and sell on day 6, provided you can make only 1 transaction i.e you can either by or you can sell.

  1. Find the local minima and store it as starting index. If not exists, return.
  2. Find the local maxima. and store it as ending index. If we reach the end, set the end as ending index.
  3. Update the solution (Increment count of buy sell pairs)
  4. Repeat the above steps if end is not reached.

Upvotes: 0

TBaggins
TBaggins

Reputation: 72

If you rearrange the logic in your inner loop, it'll work:

        if i<k:                                # Is the trade valid?
            dif.append(prices[i]-prices[k])    # Update the dif and 
            if prices[i]-prices[k]==min(dif):  # current_min arrays.
                current_min.append([i,k])

Upvotes: 1

Vijay
Vijay

Reputation: 888

Ok, as you already said the Algo is not efficient but you are interested in possible issue in current logic.

It's the inner loop for k in range(1,len(prices)): where i >= k and you append the diff in your vector dif. It results in different results for min(dif) and so incorrect results later on.

Solution is to change this loop to start with i+1.

for k in range(i + 1,len(prices)):

Upvotes: 1

Related Questions