Best time to buy and sell stock

Best Time to buy and Sell stock

这道题就是批了一层皮的Maximum subarray，只要记住利润最大值其实就是相邻两天股价相减之后的数组里面和最大的子数组，这道题考察的是最基本的动态规划（虽然我一直觉得带一个临时变量遍历数组的方法称不上动态规划）

class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        n = len(prices)
        ref = [0] * (n - 1)

        for i in xrange(1, n):
            ref[i - 1] = prices[i] - prices[i - 1]

        tmp = 0
        result = -sys.maxint
        for i in xrange(n - 1):
            if tmp + ref[i] < ref[i]:
                tmp = ref[i]
            else:
                tmp += ref[i]

            result = max(tmp, result)

        return result if result > 0 else 0

上面的思路是基于问题本质即maximum subarray来求解的，但是其实我们可以不需要额外的去构建一个股价差的数组来供我们使用，直接用一个tmp变量记录也是可以的，下面是省去了头一个for循环的写法

class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        n = len(prices)

        if n <= 1:
            return 0

        result = prices[1] - prices[0]
        tmp = prices[1] - prices[0]

        for i in xrange(2, n):
            curProfit = prices[i] - prices[i - 1]
            tmp = max(tmp + curProfit, curProfit)
            result = max(result, tmp)

        return result if result > 0 else 0

Best Time to buy and sell stock II

第二题其实比第一题更简单，因为可以多次买卖，把股价差的数组弄出来之后里面所有的正数加起来就是结果了，这道题实际上就是贪心算法，Python一行搞定

class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        return sum([prices[i] - prices[i - 1] for i in xrange(1, len(prices)) if prices[i] - prices[i - 1] > 0])

Best Time to buy and sell stock III

这道题一下子难度就不是前面两道题可以比的了，此题是一道序列型动态规划，难点在于两次买卖是最多次数，也就意味着可以只买一次，也可以不买，那这里就必须要找到二维DP的另外一个维度了，而这里的第二维度就是这个买卖代表的状态数，就这道题来说，状态有五个，下面直接把九章的图扣过来

上面的图已经把状态转移方程和其代表的意义都说明了，这里还需要注意的是序列型的惯常初始化方法就是比输入的两维各加1以表示空状态，另外这题需要dp[0]这一行除了dp[0][0]外全部设置为-sys.maxint因为这些状态不可能到达（思考一下为什么），最后dp矩阵推出来之后的结果就是奇数行里面的最大值了，下面是代码

class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        n = len(prices)
        dp = [[0] * (n + 1) for _ in xrange(6)]

        for i in xrange(1, n + 1):
            dp[0][i] = -sys.maxint

        for i in xrange(1, 6):
            for j in xrange(1, n + 1):
                if i % 2 and dp[i][j - 1] != -sys.maxint and j >= 2:
                    dp[i][j] = max(dp[i - 1][j - 1] + prices[j - 1] - prices[j - 2],
                                    dp[i][j - 1])
                elif i % 2 == 0 and j >= 2:
                    dp[i][j] = max(dp[i - 1][j - 1], dp[i - 2][j - 1] + prices[j - 1] - prices[j - 2],
                                    dp[i][j - 1] + prices[j - 1] - prices[j - 2])


        result = max(max(dp[1]), max(dp[3]), max(dp[5]))
        return result if result != -sys.maxint else 0

这里其实可以发现，实际上第一个状态如果保持下去应该全部是0，因为一直没买进卖出，所以我们可以不需要前置的缓冲状态，直接用5 * n的矩阵也是可以的，这样相反不用加很多奇怪的判断了，另外每一个状态的第一个格子肯定都是0

class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        if not prices:
            return 0

        n = len(prices)
        dp = [[0] * n for _ in xrange(5)]

        for i in xrange(1, 5):
            for j in xrange(1, n):
                if i % 2:
                    dp[i][j] = max(dp[i][j - 1] + prices[j] - prices[j - 1], dp[i - 1][j - 1], dp[i - 2][j - 1] + prices[j] - prices[j - 1])
                else:
                    dp[i][j] = max(dp[i - 1][j - 1] + prices[j] - prices[j - 1], dp[i][j - 1])

        return max(max(dp[0]), max(dp[2]), max(dp[4]))

此题还可以用O(n)的时间前后两遍遍历解决，甚至可以做到O(1)时间复杂度

O(n)的做法其实思维就是既然买两次，那我就看下买第一次之后剩下的区间买第二次能赚多少，然后我们把两段的结果加起来就是以这个点为分界进行两次买卖能得到的最佳结果，我们可以用一个array记录这些结果，还可以进一步优化到O(1)

class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        if not prices:
            return 0

        curMax, curMin = 0, prices[0]
        n = len(prices)
        array = [0] * n
        for i in xrange(1, n):
            curMax = max(curMax, prices[i] - curMin)
            curMin = min(curMin, prices[i])
            array[i] = curMax

        numMax, curMax = prices[n - 1], 0
        for i in xrange(n - 2, -1, -1):
            curMax = max(curMax, numMax - prices[i])
            numMax = max(numMax, prices[i])
            array[i] += curMax

        return max(array)

Best Time to buy and sell stock IV

第三题解决了，这道题就只是稍微改一下代码了，首先必须明确一个概念，如果输入k大于等于n/2了，此题就变成第二题了，原因也很简单，能获利的买卖策略是不可能同天买进然后抛售的，也就是说一次买卖过程至少持续两天，这么看的话只要k大于等于n/2次，其实就相当于可以在n天的范围内无限次买进卖出了，这样我们只需像第二问一样贪心求解即可，如果k小于n/2，则此问题就是第三题了，只是把5变成了k而已，里面的逻辑还是一样的，偶数次状态属于持有观望状态，奇数次属于空仓状态，下面是代码

class Solution(object):
    def maxProfit(self, k, prices):
        """
        :type k: int
        :type prices: List[int]
        :rtype: int
        """
        n = len(prices)

        if k > n / 2:
            result = 0
            for i in xrange(1, n):
                result += max(prices[i] - prices[i - 1], 0)
            return result

        dp = [[0] * (n + 1) for _ in xrange(2 * k + 2)]

        for i in xrange(1, n + 1):
            dp[0][i] = -sys.maxint

        result = -sys.maxint
        for i in xrange(1, 2 * k + 2):
            for j in xrange(1, n + 1):
                if i % 2 and dp[i][j - 1] != -sys.maxint and j >= 2:
                    dp[i][j] = max(dp[i - 1][j - 1] + prices[j - 1] - prices[j - 2],
                                    dp[i][j - 1])
                    result = max(dp[i][j], result)
                elif i % 2 == 0 and j >= 2:
                    dp[i][j] = max(dp[i - 1][j - 1], dp[i - 2][j - 1] + prices[j - 1] - prices[j - 2],
                                    dp[i][j - 1] + prices[j - 1] - prices[j - 2])


        return result if result != -sys.maxint else 0

一样，这里还是继续用2 * k + 1个状态建立维度即可，另外这里有一个dp[i - 2]的问题，当i等于1时这个地方变成了dp[-1]，由于是递推，此时dp的最后一行并没有有效结果，所以这里的错误计算实际上是被Python的语法特性掩盖了，如果是Java则这里必须加上一个i > 2的判断才行，下面是代码

class Solution(object):
    def maxProfit(self, k, prices):
        """
        :type k: int
        :type prices: List[int]
        :rtype: int
        """
        n = len(prices)
        if k >= n / 2:
            return sum([prices[i] - prices[i - 1] for i in xrange(1, n) if prices[i] > prices[i - 1]])

        dp = [[0] * n for _ in xrange(2 * k + 1)]
        result = 0

        for i in xrange(1, 2 * k + 1):
            for j in xrange(1, n):
                if i % 2:
                    dp[i][j] = max(dp[i][j - 1] + prices[j] - prices[j - 1], \
                                    dp[i - 2][j - 1] + prices[j] - prices[j - 1],\
                                    dp[i - 1][j - 1])
                else:
                    dp[i][j] = max(dp[i - 1][j - 1] + prices[j] - prices[j - 1], \
                                    dp[i][j - 1])

            if i % 2 == 0:
                result = max(result, dp[i][n - 1])

        return result

这里动态规划的迭代内循环必须是天数而不能是状态数，我们需要把一个状态到最后一天的所有结果都求出来之后才能再去求下一个状态