一、题目

题目地址：https://leetcode.com/problems/best-time-to-buy-and-sell-stock

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。

注意你不能在买入股票前卖出股票。

示例 1:

输入: [7,1,5,3,6,4]

输出: 5

解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。

示例 2:

输入: [7,6,4,3,1]

输出: 0

解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

二、求解

1、穷举法

func maxProfit(prices []int) int {
   var len int = len(prices)
   var i int
   var j int
   var rsMaxPro int = 0 //最终的最大值
   var curMaxPro int = 0 //当前最大值

   for i < len {
      j = i + 1
      curMaxPro = 0
      for j < len {
         if prices[j] > prices[i] {
            curMaxPro = prices[j] - prices[i]
            if rsMaxPro < curMaxPro {
               rsMaxPro = curMaxPro
            }
         }
         j += 1
      }

      i += 1
   }

   return rsMaxPro
}

2、图标法

通过图标发，可以得出，最大利润为波峰和波谷的差值。

func maxProfit(prices []int) int {
   var len int = len(prices)
   var i int = 1

   if len == 0 {
      return  0
   }

   var minPrice int = prices[0] //设置起点的价格
   var curMaxPro int = 0 //当前最大值

   for i < len {
      if minPrice > prices[i] {
         minPrice = prices[i]
      } else if prices[i] - minPrice > curMaxPro {
         curMaxPro = prices[i] - minPrice
      }

      i += 1
   }

   return curMaxPro
}