121. 买卖股票的最佳时机

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

解题思路

看到这种一个数组很多值，怎么得到最大值的问题，就可以往动态规划方面想了。
动态规划，如果从前往后想，还真的蛮难的，一般咱们从后往前看。
咱们把有n项时的最大收益定义为max
当把长度n的数组prices最后一个值加入计算时候，最大收益这么考虑：

  • 1、如果当前值比前一个值小，说明跌了，就不用考虑这一项了，收益和不考虑最后一项相同,还是max
  • 2、如果当前值比前一个值大，说明有涨幅，那就要考虑一下了，看看当前值-最低谷值和之前的收益哪个大，谁大选谁

那么最低谷的值怎么得到呢？很简单啦，遍历的时候，碰到更小的存下来就好啦。

  1. //动态规划，经典版，时空都是On
  2. func maxProfit(prices []int) int {
  3.     if len(prices) <= 1 {
  4.         return 0                //边界判断
  5.     }
  6.     n := len(prices)                // dp【i】【0】，第i天时，不在手；  dp【i】【1】，在手
  7.     dp := make([][2]int, n)            // dp 【】【2】 两个状态的最大值,
  8.     dp[0][1] = -prices[0]            // dp[0][1] 第0天持有==第一天买了初始股。花了钱
  10.     for i := 1; i < n; i++ {
  11.         dp[i][0] = max(dp[i-1][0], dp[i-1][1]+prices[i])
  12.         dp[i][1] = max(dp[i-1][1], -prices[i])    //在手才要承受损失，不在手谁管他是赚是亏
  13.     }
  14.     return dp[n-1][0]            //最后铁定要不在手，就是最后卖了，从零计数所以是n-1
  15. }
  17. func max(a, b int) int {
  18.     if a > b {
  19.         return a
  20.     }
  21.     return b
  22. }
//函数法，求解？ 时On，空间On
func maxProfit(prices []int) int {
    if len(prices) == 0 || len(prices) == 1 {
        return 0
    }

    //初始化最小值
    var minValue = prices[0]
    var max = 0
    for i := 0; i < len(prices); i++ {

        if prices[i] < minValue {           //1，遍历得出最小数组
            minValue = prices[i]
        }

        if prices[i]-minValue > max {
            max = prices[i] - minValue      //2，遍历找到 x-最小数组 最大的值x
        }
    }
    return max
}

//动态规划，一维函数的最值问题，最佳思路
//f(x)=x-a, 当fx Max时，x=?，求fx=

func maxProfit(prices []int) int {
    if len(prices) <= 1 {
        return 0                //边界判断
    }

    n := len(prices)
    pre, minValue_index := 0, 0     //pre = dp => fx最值;  dp[i]= 某点赚的钱

    for i := 1; i < n; i++ {
        if prices[minValue_index] > prices[i] {
            minValue_index = i                      //找最小值得索引
        }
        if prices[i] <= prices[i-1] {
            continue
        }
        pre = max(pre, prices[i] - prices[minValue_index])  //fx=本值-最小值，前面的f(x-1)
    }
    return pre
}


func max(x, y int) int {
    if x > y {
        return x
    }
    return y
}