149买卖股票的最佳时机

题目

http://www.lintcode.com/zh-cn/problem/best-time-to-buy-and-sell-stock/

假设有一个数组，它的第i个元素是一支给定的股票在第i天的价格。如果你最多只允许完成一次交易(例如,一次买卖股票),设计一个算法来找出最大利润。

样例
给出一个数组样例 [3,2,3,1,2], 返回 1

思路

• 只能进行一次操作：买->卖
• 即买低的，卖出去高，之间的利润最高；由于要先买 后卖，所以找到低的买入cmp，卖出为i,用r_max=max(r_max,i-cmp)找到最大的利润。

代码

class Solution:
    """ @param: prices: Given an integer array @return: Maximum profit """
    def maxProfit(self, prices):
        # write your code here
        if prices is None or prices==[]:return 0
        r_max= 0
        cmp = prices[0]
        for i in prices[1:]:
            #买少
            if cmp >=i:
                cmp=i
            else:
                #比较利润
                r_max=max(r_max,i-cmp)
        return r_max

150买卖股票的最佳时机II

题目

http://www.lintcode.com/zh-cn/problem/best-time-to-buy-and-sell-stock-ii/

假设有一个数组，它的第i个元素是一个给定的股票在第i天的价格。设计一个算法来找到最大的利润。你可以完成尽可能多的交易(多次买卖股票)。然而,你不能同时参与多个交易(你必须在再次购买前出售股票)。

样例
给出一个数组样例[2,1,2,0,1], 返回 2

思路

• 可以进行多次交易，但是也必须买卖买卖….
• 最大的利润：卖的都比买的大。则直接循环数组，i比i-1的大，则进行买卖

代码

class Solution:
    """ @param: prices: Given an integer array @return: Maximum profit """
    def maxProfit(self, prices):
        # write your code here
        if prices == []:return 0
        r_max=0
        for i in range(1,len(prices)):
            if prices[i] > prices [i-1]:
                r_max= r_max +prices[i]-prices[i-1]
        return r_max

151买卖股票的最佳时机III

题目

http://www.lintcode.com/zh-cn/problem/best-time-to-buy-and-sell-stock-iii/

假设你有一个数组，它的第i个元素是一支给定的股票在第i天的价格。设计一个算法来找到最大的利润。你最多可以完成两笔交易。

注意事项

你不可以同时参与多笔交易(你必须在再次购买前出售掉之前的股票)

样例
给出一个样例数组 [4,4,6,1,1,4,2,5], 返回 6

思路

• 两次交易：买卖买卖
• 可以用动态规划，第i天的两次交易=i前面的天最大价值+i后面天的最大价值，然后再从存储第i天最大价值数组中找到最大价值。
• 我们可以拆分为两种操作：之前和之后，然后再去合并找到最大价值

代码

class Solution:
    """ @param prices: Given an integer array @return: Maximum profit """
    def maxProfit(self, prices):
        if prices==[]:return 0
        #动态规划
        #前
        pre = [0 for x in prices ]
        cmp = prices[0]
        pre[0]= 0
        for i in range(1,len(prices)):
            if cmp < prices[i]:
                pre[i] = max(pre[i-1],prices[i]-cmp)
            else:
                pre[i] = pre[i-1]
                cmp = prices[i]
        #后
        las = [0 for x in prices ]
        cmp2 =prices[-1]
        las[-1]=0
        for i in range(-2,-len(prices),-1):
            if cmp2 >prices [i]:
                las [i] = max(las[i+1],cmp2-prices[i])
            else:
                las[i] = las[i+1]
                cmp2= prices[i]
        #第i天的价格=前+后；取所有天数的最大值
        #合并找到最大价值。
        result =0 
        for i in range(len(prices)):
            result = max(result , pre[i]+las[i])
        return result

阅读更多

更多精彩内容