122. 买卖股票的最佳时机 II - 力扣（LeetCode） (leetcode-cn.com)
难度：中等
题目描述：给定一个数组 prices ，其中 prices[i] 是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
分析
贪心.png
dp.png
此题是121题的进阶，
121题实质计算的是一次交易的最大利润，而122题不限制交易次数，计算的是总体最大利润
此题有两种解题思路
1- 使用贪心算法
对于本题来说使用贪心算法，将数组中局部最优解相加，最后构成全局最优解
例如：数组[7,1,5,3,6,4],一次交易的全局最优解可以通过121题可知
而局部最优解为[1,5] 和 [3.6] 可以通过图看出，这都是单调递增区间，将两次交易利润相加就是全局最优解
2- 使用动态规划
由于题目中提到不能同时参与多笔交易，所以每天存在两种状态，一种是手里有一只股票，一种是手中没有股票
所以可以根据交易状态确定dp数组
dp[i][j]表示第i天，交易状态为j的最大利润，此处i为数组长度，j为状态值即0，1
dp数组如图所示
举个简单的例子：
初始资金为100
第一天股票价格为7，即prices[0]=7
此时有两个选择，1持有股票，2不持有，对应dp数组中的j下标
如果此时不持有股票，表示我们并没有购买，所以此时利润为0，即dp[0][0]=0
如果此时持有股票，表示我们花7元买了一股，此时利润为-7，即dp[0][1]=-7
此时dp数组进行初始化完成，但后续需要找到特定表达式，计算当前最佳利润
第二天股票价格为1，即prices[1]=1
如果此时选择不持有股票，这时有两种情况，
第一，昨天不持有股票，今天也不持有股票，则我们本金并没有变化，即利润为0；
第二，昨天持有股票，今天不持有股票，表示我们昨天花7元买了股票，剩余本金93元，今天股价1元，我们卖出，则本金94元，即利润为-6。
由于我们需要计算当前选择的利润最大值，所以我们取两个选择的最大值为今日选择不持有股票的最大利润，即dp[1][0] = max(dp[0][0],dp[0][1]+prices[1]) = 0
如果此时选择持有股票，也存在两种情况
第一，昨天不持有股票，今天持有股票，表示我们今天花1元购买一股，即利润为-1；
第二，昨天持有股票，今天继续持有股票，依然是昨天7元一股买的股票，由于股票跌了在没有卖出之前并不影响自己本身的利润，所以利润依旧是-7
由于我们需要计算当前选择的利润最大值，所以我们取两个选择的最大值为今日选择不持有股票的最大利润，即dp[1][1] = max(dp[0][0]-prices[1],dp[0][1]) = -1
第三天股票价格为5，即prices[2]=5
根据第二天推理可得
dp[2][0] = 4
dp[2][1] = -1
所以最后dp数组如图所示
解题
贪心
class Solution {
public int maxProfit(int[] prices) {
if (prices == null || prices.length <= 1) return 0;
int ans = 0;
for (int i = 1; i < prices.length; i++) {
if (prices[i] > prices[i-1]) { // 卖出有利可图
ans += (prices[i] - prices[i-1]);
}
}
return ans;
}
}
动态规划
class Solution {
public int maxProfit(int[] prices) {
int[][] dp = new int[prices.length][2];
dp[0][0] = 0;
dp[0][1] = -prices[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][0] - prices[i], dp[i-1][1]);
System.out.println(dp[i][0] + " " + dp[i][1]);
}
return dp[prices.length-1][0];
}
}
