Best Time to Buy and Sell Stock

Question

Say you have an array for which the $$i_{th}$$ 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.

Tag

• Array
• Dynamic Programming

Thought

There are two ways to solve the problem:

1. Without DP: use each number in the prices list to subtract the minimal price in the previous subarray.
2. With DP: use the DP table to store the previous maximum profit and compare the result by subtracting between the current item and the minimal number in the previous subarray. The recurrent equation is below: DP[i] = max(prices[i] - min(prices[:i]), DP[i - 1])

Code

Without DP:

class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        minp = float('inf')
        prof = 0
        for i in prices:
            if i <= minp:
                minp = i
                continue
            if i > minp:
                prof = max( prof, i - minp )
        return prof

With DP:

class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        length = len(prices)
        DP = [0 for i in xrange(length)]
        if length <= 1:
            return 0
        DP[0] = 0
        minValue = prices[0]
        for i in xrange(1, length):
            price = prices[i]
            DP[i] = max(price - minValue, DP[i - 1])
            if minValue > price:
                minValue = price
        return DP[-1]