[Leetcode][python]Best Time to Buy and Sell Stock I/II/III/买卖股票的最佳时机

不念不忘少年蓝@ 2022-06-06 10:42 77阅读 0赞

# 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次交易。