Day15

昨晚咨询了师兄面试算法岗问的问题；有点慌呀。现在的机试都不问leetcode上的题了，而是更加贴近于深度学习的问法，譬如，写一个算法检测出图片中最大的人脸框。我该看看牛客网上今年的机试题了。

121. Best Time to Buy and Sell Stock
     **思路：只能买卖一次，挑选差值最大的一组。

这种直观的思路超时了。

class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        tmp = [0 for x in range (len(prices)-1)] 
        for i in range(0,len(prices)-1):
            tmp[i] = prices[len(prices)-1]-prices[i]
             
        return max(self.maxProfit(prices[0:len(prices)-1]),max(tmp))

动态规划解题，从新添的点里找最低买入点，从新添的点里找最高利润差。

class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        if len(prices) <=1:
            return 0
        buy_price = prices[0]
        max_profit = 0
        for i in range(1,len(prices)):
            buy_price = min(buy_price, prices[i])
            max_profit = max(max_profit, prices[i]-buy_price)
        return max_profit

122. Best Time to Buy and Sell Stock II
     **思路：可以买卖多次，但是交易不能同时进行，只能卖完上一注股票才能买入。所以只要找到有增加的值，就算进去。累加得最大利润。

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