给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易(即买入和卖出一支股票一次),设计一个算法来计算你所能获取的最大利润。
注意:你不能在买入股票前卖出股票。
示例 1:
1 | 输入: [7,1,5,3,6,4] |
示例 2:
1 | 输入: [7,6,4,3,1] |
方法一:暴力法
1 | class Solution { |
复杂度分析:时间复杂度为$O(n^2)$,空间复杂度为O(1)。其中,n为数组prices的长度。
方法二:动态规划
计算最大的卖出价格
思路:用数组dp来存储第i天以后最大的卖出价格,从后往前计算
$$
dp[i] = \max(dp[i+1], prices[i+1])
$$
从而,最大利润为
$$
profit = \max(dp[i] - prices[i])
$$
1 | class Solution { |
复杂度分析:时间复杂度和空间复杂度均为O(n)。其中,n为数组prices的长度。
计算最小的买入价格
解法
思路:用数组dp来存储第i天以前最小的买入价格,状态转移方程如下
$$
dp[i] = \min(dp[i-1],\ prices[i-1])
$$
从而,最大利润为
$$
profit = \max(prices[i] - dp[i])
$$
1 | class Solution { |
复杂度分析:时间复杂度和空间复杂度均为O(n)。其中,n为数组prices的长度。
优化
由于dp[i]只与dp[i-1]以及prices[i-1]有关系,因此,不需要存储第0~i-2项。
1 | class Solution { |
复杂度分析:时间复杂度为O(n),空间复杂度为O(1)。其中,n为数组prices的长度。