题目描述
给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易(多次买卖一支股票)。
注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。
示例 1:
输入: [7,1,5,3,6,4]
输出: 7
解释:
在第 2 天(股票价格 = 1)的时候买入,在第 3 天(股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。 随后,在第 4 天(股票价格 = 3)的时候买入,在第 5 天(股票价格 = 6)的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。
示例 2:
输入: [1,2,3,4,5]
输出: 4
解释: 在第 1 天(股票价格 = 1)的时候买入,在第 5 天 (股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。 注意你不能在第 1 天和第 2 天接连购买股票,之后再将它们卖出。 因为这样属于同时参与了多笔交易,你必须在再次购买前出售掉之前的股票。
示例 3:
输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
1.暴力搜索
暴力搜索也叫回溯法:
public class Solution {
private int res;
public int maxProfit(int[] prices) {
int len = prices.length;
if (len < 2) {
return 0;
}
this.res = 0;
dfs(prices, 0, len, 0, res);
return this.res;
}
/**
* @param prices 股价数组
* @param index 当前是第几天,从 0 开始
* @param status 0 表示不持有股票,1表示持有股票,
* @param profit 当前收益
*/
private void dfs(int[] prices, int index, int len, int status, int profit) {
if (index == len) {
this.res = Math.max(this.res, profit);
return;
}
dfs(prices, index + 1, len, status, profit);
if (status == 0) {
// 可以尝试转向 1
dfs(prices, index + 1, len, 1, profit - prices[index]);
} else {
// 此时 status == 1,可以尝试转向 0
dfs(prices, index + 1, len, 0, profit + prices[index]);
}
}
}
2.贪心算法
这道题的贪心算法流程:
res = (prices[3] - prices[2]) + (prices[2] - prices[1]) + (prices[1] - prices[0])
= prices[3] - prices[0]
其实就有点像官方解法的暴力搜索吧。
public class Solution {
public int maxProfit(int[] prices) {
int res = 0;
int len = prices.length;
for (int i = 0; i < len - 1; i++) {
int diff = prices[i + 1] - prices[i];
if (diff > 0) {
res += diff;
}
}
return res;
}
}
关键是要证明这是正确的:
3.动态规划
第 1 步:定义状态
状态 dp[i][j] 定义如下:
第一维 i 表示索引为 i 的那一天(具有前缀性质,即考虑了之前天数的收益)能获得的最大利润;
第二维 j 表示索引为 i 的那一天是持有股票,还是持有现金。这里 0 表示持有现金(cash),1 表示持有股票(stock)。
第 2 步:思考状态转移方程
状态从持有现金(cash)开始,到最后一天我们关心的状态依然是持有现金(cash)
说明:
因为不限制交易次数,除了最后一天,每一天的状态可能不变化,也可能转移;
写代码的时候,可以不用对最后一天单独处理,输出最后一天,状态为 0 的时候的值即可。
第 3 步:确定起始
起始的时候:
如果什么都不做,dp[0][0] = 0;
如果买入股票,当前收益是负数,即 dp[0][1] = -prices[i];
第 4 步:确定终止
终止的时候,上面也分析了,输出 dp[len - 1][0],因为一定有 dp[len - 1][0] > dp[len - 1][1]。
public class Solution {
public int maxProfit(int[] prices) {
int len = prices.length;
if (len < 2) {
return 0;
}
// 0:持有现金
// 1:持有股票
// 状态转移:0 → 1 → 0 → 1 → 0 → 1 → 0
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]);
dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
}
return dp[len - 1][0];
}
}
Reference
https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii
https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/solution/tan-xin-suan-fa-by-liweiwei1419-2/