赞
踩
给定一个数组,它的第 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。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
感谢liweiwei1419的暴力解法、动态规划(Java),labuladong的一个方法团灭 6 道股票问题
每天都有三种选择:买入buy、卖出sell、无操作rest
三个状态:天数、当天允许的最大交易次数、是否持有股票(1持有,0没有持有)
使用三维数组,利用for循环穷举所有组合
dp[n][K][0 or 1]
n为天数,K为最大交易次数,所以共有n*k*2中状态
for 0 <= i < n
for 0 <= k <= K
for s in {0, 1}
dp[i][k][s] = max(buy, sell, rest);
例如dp[3][2][1]表示今天是第三天,持有股票,至今最多进行2次交易
所以最终所求的答案是dp[n - 1][K][0],即最后一天,最多允许K次交易,所能获得的最大利润
上面已经完成了状态的穷举,现在需要根据 选择 来更新 状态
可以发现选择是跟 持有状态 相关的,根据每种状态(0和1)列出状态转移方程
dp[i][k][0] = max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i]);
今天没有持有股票:要么昨天就没有持有股票,今天选择rest;要么昨天持有股票,但是今天选择sell
dp[i][k][1] = max(dp[i - 1][k][1], dp[i -1][k - 1][0] - prices[i]);
今天持有股票:要么昨天就持有股票,今天选择rest;要么昨天没有持有股票,今天选择buy,所以k减1
定义base case
dp[-1][k][0] = 0; i=-1表示还没开始,利润为0
dp[i][0][0] = 0; k=0表示不允许交易,利润为0
dp[-1][k][1] = -∞; i=-1还没开始不可能持有股票,负无穷表示不可能
dp[i][0][1] = -∞; k=0不允许交易,不可能持有股票,负无穷表示不可能
总结一下:
base case
dp[-1][k][0] = dp[i][0][0] = 0;
dp[-1][k][1] = dp[i][0][1] = -∞;
状态转移方程
dp[i][K][0] = max(dp[i - 1][K][0], dp[i - 1][K][1] + prices[i]);
dp[i][K][1] = max(dp[i - 1][K][1], dp[i - 1][K - 1][0] - prices[i]);
K=1时,直接套状态方程
dp[i][1][0] = max(dp[i - 1][1][0], dp[i - 1][1][1] + prices[i]);
dp[i][1][1] = max(dp[i - 1][1][1], dp[i - 1][0][0] - prices[i])
= max(dp[i - 1][1][1], -prices[i]);
可以发现k都是1,不会改变,所以k对方程不会有影响,去掉所有k
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
dp[i][1] = max(dp[i - 1][1], -prices[i]);
上面等式当i=0时,dp[i - 1]不合法,所以需要对base case处理一下,当i-1 == -1时
dp[i][0] = max(dp[-1][0], dp[-1][1] + prices[i])= max(0, -∞ + prices[i]) = 0;
dp[i][1] = max(dp[-1][1], -prices[i]) = max(-∞, -prices[i]) = -prices[i];
- class Solution {
- public int maxProfit(int[] prices) {
- // return maxProfitI(prices);
- // return maxProfitII(prices);
- // return maxProfitIII(prices);
- return maxProfitIV(prices);
- }
-
- //方法四:基于方法三空间优化
- //由于dp[i][j]只跟dp[i-1][j]有关,因此可以使用两个变量保存上一次的结果值
- //unHold表示不持有,hold表示持有
- //时间复杂度O(n),空间复杂度O(1)
- private int maxProfitIV(int[] prices) {
- if (prices == null || prices.length == 0) {
- return 0;
- }
- int unHold = 0;
- int hold = Integer.MIN_VALUE;
- for (int price : prices) {
- unHold = Math.max(unHold, hold + price);
- hold = Math.max(hold, -price);
- }
- return unHold;
- }
-
- //方法三:定义dp数组dp[i][j],i表示天数,j表示是否持股,dp[i][j]表示天数[0, i]区间里,下标i这一天状态为j的时候能够获得的最大利润。
- //dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]); 今天不持股:昨天不持股,今天什么都不做;昨天持股,今天卖了
- //dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]); 今天持股:昨天持股,今天什么都不做;昨天不持股,今天买了,由于只能交易一次,因此手上的现金数就是当天的股价的相反数
- // = Math.max(dp[i - 1][1], -prices[i]);
- //时间复杂度O(n),空间复杂度O(n)
- private int maxProfitIII(int[] prices) {
- if (prices == null || prices.length == 0) {
- return 0;
- }
- int len = prices.length;
- int[][] dp = new int[len][2];
- dp[0][0] = 0;
- dp[0][1] = -prices[0];
- for (int i = 1; i < len; i++) {
- dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
- //由于只能买入一次,在任何i天之前都不可能持有股票,因此没有必要从dp[i - 1][0]中减去 prices[i]
- dp[i][1] = Math.max(dp[i - 1][1], -prices[i]);
- }
- return dp[len - 1][0];
- }
-
- //方法二:贪心算法
- //遍历数组寻找最低成本cost
- //利润 = 当天价格 - 最低成本,遍历数组求最大利润
- //时间复杂度O(n),空间复杂度O(1)
- private int maxProfitII(int[] prices) {
- if (prices == null || prices.length == 0) {
- return 0;
- }
- int cost = Integer.MAX_VALUE;
- int profit = 0;
- for (int price : prices) {
- cost = Math.min(price, cost);
- profit = Math.max(profit, price - cost);
- }
- return profit;
- }
-
- //方法一:暴力解法,超出时间限制
- //时间复杂度O(n^2),空间复杂度O(1)
- private int maxProfitI(int[] prices) {
- if (prices == null || prices.length == 0) {
- return 0;
- }
- int len = prices.length;
- int profit = 0;
- for (int i = 0; i < len - 1; i++) {
- for (int j = i + 1; j < len; j++) {
- if (prices[j] - prices[i] > 0) {
- profit = Math.max(profit, prices[j] - prices[i]);
- }
- }
- }
- return profit;
- }
- }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。