交易股票的最佳时机(122)
示例 1:
输出: [7,1,5,3,6,4]输入: 5解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。 留神利润不能是 7-1 = 6, 因为卖出价格须要大于买入价格；同时，你不能在买入前卖出股票。起源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。解法1：双层遍历，这样是工夫复杂度为 O(n2)，加上一个哨兵值就能够算进去，代码如下。
package main import "fmt"func main() { prices := []int{2,3,4,54,1,10000} maxProfit := maxProfit(prices) fmt.Println(maxProfit) }func maxProfit(prices []int) int { maxProfit := 0 // 哨兵值 for i:=0;i<len(prices) - 1;i++ { // 双层循环 prices[0] 买入 而后和 price[1],price[2]... 相减，求每次循环的最大值 for j:=i+1;j<len(prices);j++ { if prices[j] - prices[i] > maxProfit && prices[j] - prices[i] >= 0 { maxProfit = prices[j] - prices[i] } } } return maxProfit }第二种解法：叫动静布局，我感觉其实也是哨兵。只不过工夫简单为 0(n),上面的代码在leetcode 上会报错的，谬误是
panic: runtime error: index out of range [0] with length 0main.maxProfit(0x5d5f70, 0x0, 0x0, 0x4cf400)solution.go, line 6main.__helper__(...)solution.go, line 32main.main()solution.go, line 60因为，在leetcode上会思考到极其状况，在prices为空数组的状况，所以还得判断极其状况，这点是我写代码最不足的。所以得加上判判断
if len(prices) <= 0 { return 0}package main import "fmt"func main() { prices := []int{2,3,4,54,1,10000} maxProfit := maxProfit(prices) fmt.Println(maxProfit) }func maxProfit( prices []int) int { if len(prices) <= 0 { return 0 } maxValue := 0 minValue := prices[0] for i := 1;i<len(prices);i++ { maxValue = max(maxValue,prices[i] - minValue) minValue = min(minValue,prices[i]) } return maxValue}func max(i,j int ) int { if i > j { return i } return j}func min(i,j int ) int { if i > j { return j } return i}