Best Time to Buy and Sell Stock

题目大意

给定每天的股票价格，如果只允许进行一轮交易，也就是买进一次和卖出一次，求所能获得的最大的利润。

解题思路

DP或者直接解决

代码

DP

dp[i] = max(dp[i - 1], prices[i] - minPrice)
minPrice永远是之前的最底价格

class Solution(object):
    def maxProfit(self, prices):
        """ :type prices: List[int] :rtype: int """      
        if not prices:
            return 0
        dp = [0 for __ in range(len(prices))]
        minPrice = prices[0]
        for i in range(1, len(prices)):
            dp[i] = max(dp[i - 1], prices[i] - minPrice)
            if(minPrice > prices[i]):
                minPrice = prices[i]
        return dp[-1]

直接解法

本题由于思路比较简单，可以直接解决

class Solution(object):
    def maxProfit(self, prices):
        """ :type prices: List[int] :rtype: int """      
        if not prices : 
            return 0
        ans, money, n = 0, prices[0], len(prices)
        for i in range(n):
            ans = max(ans, prices[i]-money)
            money = min(prices[i], money)
        return ans

Best Time to Buy and Sell Stock II

题目大意

允许进行多次交易，即可以多次买入和卖出，但手中最多只能持有一支股票，在再次买入的时候必须将之前的股票卖出，求能获取的最大利润。

解题思路

贪心法，每次在递增序列就算入，一旦降价，就在上一个节点抛出，其实代码就是直接统计递增的序列

代码

class Solution:
    # @param prices, a list of integer
    # @return an integer
    def maxProfit(self, prices):
        maxprofit = 0
        for i in range(1, len(prices)):
            if prices[i] >= prices[i-1]:
                maxprofit += prices[i] - prices[i-1]
        return maxprofit

Best Time to Buy and Sell Stock III

题目大意

给定每天的股票价格，如果最多允许两次交易，但手中最多只能持有一支股票，在再次买入的时候必须将之前的股票卖出，求能获取的最大利润。

解题思路

动态规划，开辟两个数组f1和f2，f1[i]表示在price[i]之前进行一次交易所获得的最大利润，f2[i]表示在price[i]之后进行一次交易所获得的最大利润。则f1[i]+f2[i]的最大值就是所要求的最大值（代码中则是从后往前寻找降幅最大）。

两个dp，dp1类似第一题，dp2反过来扫描下降幅度最大，保持maxPrice

代码

class Solution(object):
    def maxProfit(self, prices):
        """ :type prices: List[int] :rtype: int """
        length = len(prices)
        if length==0: 
            return 0
        f1 = [0 for __ in range(length)]
        f2 = [0 for __ in range(length)]
        # 从前往后最大利润
        minPrice = prices[0]
        for i in range(1, length):
            f1[i] = max(f1[i-1], prices[i]-minPrice)
            minPrice=min(minPrice, prices[i])
        # 从后往前则是最小利润
        maxPrice = prices[length-1]
        for i in range(length-2,-1,-1):
            f2[i] = max(f2[i+1], maxPrice-prices[i])
            maxPrice = max(maxPrice, prices[i])

        maxProfit=0
        for i in range(length):
            if f1[i]+f2[i] > maxProfit: 
                maxProfit = f1[i]+f2[i]
        return maxProfit

总结

该类题目还有很多解法，有空可以对比看看，第三题严格来说并不能延伸到n次交易。