Best time to buy and Sell Stock- Another approach in Python

user_12531409 0
Viewed 6387

QUESTION-Say you have an array for which the ith element is the price of a given stock on dayi.

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.

Example 1:

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.

Example 2:

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

I believe that this problem can be solved using dynamic programming and before moving on to the solution simply ,I tried to solve this problem using my own approach . I did checked out the brute force algorithm and realized that my approach is not similar to brute force

public class Solution {
    public int maxProfit(int prices[]) {
        int maxprofit = 0;
        for (int i = 0; i < prices.length - 1; i++) {
            for (int j = i + 1; j < prices.length; j++) {
                int profit = prices[j] - prices[i];
                if (profit > maxprofit)
                    maxprofit = profit;
            }
        }
        return maxprofit;
    }
}

Here ,is my approach

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        res=0
        if not prices:
            return 0
        idx=prices.index(min(prices))
        value=min(prices)
        try:
            for i in range (idx+1,len(prices)):
                res=max(res,prices[i]-value)
        except IndexError :
            return 0
        return res

My code passed the sample test case and 143/200 cases and fails for this one .

Input: [2,4,1]
Output: 0
Expected: 2

How can I improve my code ? How can I make this approach work ? or if this approach is totally wrong please elaborate .

I believe the time complexity of my approach is better than the brute force and therefore,to struggle and make this code work;later check out the dynamic programming approach as well

dynamic-programming time-complexity algorithm python
4 Answers
def max_profit(prices):
    if not prices:
        return 0

    max_prof = 0
    min_price = prices[0]

    for i in range(1, len(prices)):
        if prices[i] < min_price:
            min_price = prices[i]
        max_prof = max(max_prof, prices[i] - min_price)
    return max_prof

Output:

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

The most efficient algorithm is O(N) time and O(1) space for this question and it can't get anymore efficient than that, because here we have to visit each element at least once:

class Solution:
    def maxProfit(self, prices):
        if not prices:
            return 0

        max_price = 0
        min_price = float('inf')
        for i in range(len(prices)):
            if prices[i] < min_price:
                min_price = prices[i]
            if prices[i] > max_price:
                max_price = max(max_price, prices[i] - min_price)
        return max_price

References

  • For additional details, you can see the Discussion Board. There are plenty of accepted solutions, explanations, efficient algorithms with a variety of languages, and time/space complexity analysis in there.
user_65533280

You don't need dynamic programming for this question. You want to find the maximum value of x[i] - (min price up to i). So, to find the selling time, you just evaluate (if you were dealing with numpy arrays) sell = np.argmax(x- np.minumum.accumulate(x)) For the buying time you need `np.argmin(x[:sell])

If you are working with vanilla python (no numpy) just implement the cumulative minimum and argmin/argmax (pretty trivial).

user_29772560

I am not good at python, but i can show you how i'll do it java.

public int maxProfit(int[] prices) {
    int n = prices.length;
    if(n==0) return 0;
    int[] L = new int[n];
    int[] R = new int[n];
    L[0]=prices[0];
    for(int i=1;i<n;i++){
        L[i]=Math.min(L[i-1], prices[i]);
    }
    R[n-1]=prices[n-1];
    for(int i=n-2;i>=0;i--){
        R[i]=Math.max(R[i+1], prices[i]);
    }
    int max=Integer.MIN_VALUE;
    for(int i=0;i<n;i++){
        max = Math.max(max, R[i]-L[i]);
    }
    return max;
}

This approach is basically based on Trapping rain water problem.

user_118966640
Related