- 原题链接:121. 买卖股票的最佳时机
题目
给定一个数组 prices ,它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票,并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润,返回 0 。
示例 1:
输入:[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 <= 105
- 0 <= prices[i] <= 104
1- 思路
利用动规五部曲
🔑1. 定义dp数组,并理解dp数组的含义
dp[i][0]
表示在第i
天结束时,手上持有股票的最大利润。dp[i][1]
表示在第i
天结束时,手上不持有股票的最大利润。
🔑2. 确定递推公式
- 对于
dp[i][0]
的更新,Math.max(dp[i-1][0], -prices[i])
- 表示比较 前一天持有股票的最大利润 和在 当天买入股票的情况(此时的利润为
-prices[i]
),选择二者中的较大值作为当前持有股票的最大利润。
- 表示比较 前一天持有股票的最大利润 和在 当天买入股票的情况(此时的利润为
- 对于
dp[i][1]
的更新,Math.max(dp[i-1][1], dp[i-1][0] + prices[i])
- 表示比较 前一天不持有股票的最大利润 和在 当天卖出股票的情况(此时的利润为
dp[i-1][0] + prices[i]
,即前一天持有股票的最大利润加上今天卖出股票获得的利润),选择二者中的较大值作为当前不持有股票的最大利润。
- 表示比较 前一天不持有股票的最大利润 和在 当天卖出股票的情况(此时的利润为
🔑3. dp数组初始化
dp[0][0]
被设置为-prices[0]
,意味着在第一天买入股票的情况下的利润(花费了prices[0]
)dp[0][1]
被设置为0
,表示在第一天没有进行任何操作的情况下的利润(即不持有股票)
🔑4. 确定遍历顺序
- 由于
dp[i][0]
和dp[i][1]
的计算都依赖于i-1
天的状态,因此数组的遍历顺序应该是从前向后遍历。
🔑5. 举例推导dp数组
2- 题解
⭐买卖股票的最佳时机 ——代码实现思路
class Solution {
public int maxProfit(int[] prices) {
int[][] dp = new int[prices.length][2];
// 初始化
dp[0][0] = -prices[0];
dp[0][1] = 0;
for(int i = 1;i < prices.length;i++){
dp[i][0] = Math.max(dp[i-1][0],-prices[i]);
dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0]+prices[i]);
}
return dp[dp.length-1][1];
}
}
复杂度分析
时间复杂度
- 遍历价格数组: 算法的主要部分是一个for循环,该循环一次遍历prices数组
O(n)
空间复杂度
- 算法的空间复杂度主要由dp数组占用的空间决定,为
O(n)
3- ACM 模式
public class hot76_maxProfit {
public static int maxProfit(int[] prices){
//
int[][] dp = new int[prices.length][2];
dp[0][0] = -prices[0];
dp[0][1] = 0;
for(int i = 1 ; i < prices.length;i++){
dp[i][0] = Math.max(dp[i-1][0],-prices[i]);
dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0]+prices[i]);
}
return dp[dp.length-1][1];
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println("输入数组长度");
int n = sc.nextInt();
int[] prices = new int[n];
System.out.println("输入 prices 数组元素");
for(int i = 0; i < n;i++){
prices[i] = sc.nextInt();
}
System.out.println("最大利润"+maxProfit(prices));
}
}