Poison

122. Best Time to Buy and Sell Stock II

DP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public int maxProfit(int[] prices) {
// 定义 dp[i][0] 为第 i 天休市且持有当日股票时的最大利润
// 定义 dp[i][1] 为第 i 天休市且未持有当日股票时的最大利润
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], dp[i - 1][1] - prices[i]);
dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i]);
}

return dp[prices.length - 1][1]; // 最后一天休市时不持有股票利润最大
}
}
Greedy
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public int maxProfit(int[] prices) {
int maxProfit = 0;
for (int i = 1; i < prices.length; i++) {
if (prices[i] > prices[i - 1]) {
// 第 i 天的股票价格高于第 i - 1 天,我们需要在第 i - 1 天买入股票
maxProfit += prices[i] - prices[i - 1];
}
}

return maxProfit;
}
}

可以理解为我们可以回到昨天,以今天的股票价格来决定昨天是否需要买入股票以使利润最大化。

Reference

122. Best Time to Buy and Sell Stock II