121.买卖股票的时机

• • • 题目
    • 方法一：暴力解决
    • • 思路
      • 代码
      • 运行结果
    • 方法二：固定一端
    • • 思路
      • 代码
      • 运行结果
    • 方法三：使用动态规划
    • • 思路
      • 代码
      • 运行结果

'''
Description: 121.买卖股票的最佳时机
Autor: 365JHWZGo
Date: 2021-12-08 20:36:09
LastEditors: 365JHWZGo
LastEditTime: 2021-12-08 21:55:30
'''

通过控制头指针和尾指针来寻找最大差值。

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

从思路一可以看出利润最大值之和当前来说最低买入和最高卖出有关，那么我们是不是可以确定一头，遍历另一头。

class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        #买入点
        buyPoint = prices[0]
        #最大利润
        maxProfit = 0
        #依次遍历卖出点，因为卖出点不能和买入点同一天，所以从第二天开始
        for i in range(1,len(prices)):
            sellPoint = prices[i]            
            if sellPoint-buyPoint>=0:
                maxProfit = max(sellPoint-buyPoint,maxProfit)   
                # 当当前买入点比以前确定的买入点低，则重新赋值    
                if buyPoint>prices[i]:
                    buyPoint = prices[i]
            else:
                buyPoint = sellPoint
        return maxProfit  

        1.确定dp数组以及下标含义
            dp[i]代表第i天的最大收益
        2.确定递推公式
            dp[i]=max(prices[i]-prices[buyPoint],dp[i-1])
        3.初始化dp数组
            dp[0]=0
            第0天的最大收益为0
            dp数组全部初始化为0
        4.确定遍历顺序
            从前往后依次遍历
        5.举例推导
            EG：prices=[7,1,5,3,6,4]
            dp   [0, 0, 4, 4, 5, 5]
            5

class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        dp = [0]*len(prices)
        dp[0] = 0
        buyPoint = 0
        for i in range(1,len(prices)):
            if prices[i]-prices[buyPoint] <= 0:
                buyPoint = i
            dp[i] = max(prices[i]-prices[buyPoint],dp[i-1])
        # print(dp)
        return dp[-1]