题目描述.png
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii
1. 贪心算法
贪心算法是当前最优解。按照题目描述：若是今天的比昨天大，那么就可以卖出。
/**
* 贪心算法(只要今天大于昨天的股票价格，就卖出)
*/
public int maxProfit(int[] prices) {
//只要今天比昨天高，那么就卖出
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;
}
2. 动态规划
动态规划（DP）是获取最优解，通常需要先进行暴力搜索，而后去冗余。一般可以使用dp数组来保存某个阶段的最优解。
分析上面数组，每天有两种状态。买入和抛出。若最后一天不持有股票，那么则是最优解。
使用一个二维数组（DP），来记录每天最优状态。
- 第i天不持有股票有两种可能，一种是第1-1天不持有股票，另一种是第i-1天持有股票，但是第i天抛出。
- 第i天持有股票也有两种可能，一种是第i-1天便持有股票，另一种是第i-1天不持有股票，但是第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]);
那么便可结算出i天的最优解。
/**
* 动态规划，若最后一天不持有股票，则是最优解
*/
public int maxProfit(int[] prices) {
if (prices == null || prices.length == 0) {
return 0;
}
//长度
int[][] dp = new int[prices.length][2];
//第0天不持有股票，第0天持有股票，那么它为-prices[0]
dp[0][0] = 0;
dp[0][1] = -prices[0];
for (int i = 1; i < prices.length; i++) {
//第i天不持有股票(两种情况，第i-1天不持有股票，或第i-1天持有股票，但是第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][0];
}
