题目描述

给定一个数组，它的第 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。

算法

本题使用动态规划的方式

动态规划的核心部分是定义状态，状态转移方程，以及存储中间结果

在本题中一个状态就是卖出股票的日期在买进股票的日期之后，并且卖出股票的价格大于或者等于买进股票的价格

状态转移方程就是当可以以更低的价格买进股票时，就转移到一个新的状态

存储的中间结果就是在状态转移之前保存之前的最大收益

遍历一遍数组：

首先买进和卖出都指向第一天的价格

然后到了后一天，后一天的价格有如下三种形式：

  • 价格比之前的卖出价格高，那么更新卖出价格
  • 价格在之前的卖出价格与买进价格之间，那么不做处理，直接等待新的一天到来
  • 价格比之前的买进价格低，那么将之前的卖出价格与买进价格作差，这个差值就是收益，将这个收益与之前保存的最大作比较，如果这个收益更大，就更新存储的最大收益，然后将买进和卖出的价格都指向当前这个更低的买进价格。

代码

func maxProfit(prices []int) int {
	if len(prices) == 0 {
		return 0
	}
	big, small := prices[0], prices[0]
	max := big - small
	for index, value := range prices {
		if value >= big {
			big = value
		}
		if value < small {
			// 保存之前的最大值
			if max < (big - small) {
				max = big - small
			}
			big, small = value, value
		}
		// 到了数组最后,看最大收益是否需要更新
		if index == len(prices)-1 {
			if max < (big - small) {
				max = big - small
			}
		}
	}
	return max
}