121. 买卖股票的最佳时机

题目描述：

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择某一天买入这只股票，并选择在未来的某一个不同的日子卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0。

示例 1：

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

示例 2：

输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 没有交易完成, 所以最大利润为 0。

提示：

• 1 <= prices.length <= 10^5
• 0 <= prices[i] <= 10^4

---

解题分析及思路：

对于这个问题，我们可以使用动态规划的思想。我们定义状态 dp[i] 表示第 i 天卖出股票所能获取的最大利润，那么状态转移方程可以表示为： dp[i] = max(dp[i-1], prices[i] - minPrice)

其中 minPrice 表示前 i-1 天中的最低股票价格。通过遍历数组，不断更新最低价格和最大利润，最终得到的 dp[len(prices)-1] 即为最大利润。

那么对应动态规划解法：

1. 定义状态： 在这个问题中，状态可以定义为到达每个位置时的不同路径数量。我们使用一维数组 dp 表示状态，其中 dp[i] 表示第 i 天卖出股票所能获取的最大利润。

2. 找到状态转移方程： 每次只能选择某一天买入，然后在未来的某一天卖出，所以在第 i 天卖出股票的最大利润等于前一天卖出股票的最大利润和第 i 天股票价格减去前 i-1 天最低股票价格的较大值。

dp[i] = max(dp[i-1], prices[i] - minPrice)

3. 初始化： 在初始化阶段，我们将 minPrice 初始化为第一天的股票价格。

4. 递推求解： 通过遍历数组，根据状态转移方程计算到达每个位置的最大利润。

5. 计算最终结果： 最终结果即为 dp[len(prices)-1]，表示最后一天卖出股票所能获取的最大利润。

func maxProfit(prices []int) int {
	var min = prices[0]
	var max = func(i, j int) int {
		if i > j {
			return i
		}
		return j
	}
	var dp = make([]int, len(prices))
	for i := 1; i < len(prices); i++ {
		if min > prices[i] {
			min = prices[i]
		}
		dp[i] = max(dp[i-1], prices[i]-min)
	}
	return dp[len(prices)-1]
}

复杂度：

• 时间复杂度：O(N)，其中 N 为数组 prices 的长度。
• 空间复杂度：O(N)，其中 N 为数组 prices 的长度。。

执行结果：

• 执行耗时:94 ms,击败了85.62% 的Go用户
• 内存消耗:7.7 MB,击败了80.61% 的Go用户