121. Best Time to Buy and Sell Stock
121
这个比较简单，大致思想：
1.如果sale-buy<=0，则该价格适合买入。
2.否则判断该价格卖出的价格是否最好。
代码如下：
public int maxProfit(int[] prices) {
if(prices==null||prices.length==0){
return 0;
}
int res = 0;
int buy = prices[0];
for(int i=1;i<prices.length;i++){
if(prices[i]-buy<=0){
buy=prices[i];
}else{
res = Math.max(res,prices[i]-buy);
}
}
return res;
}
122. Best Time to Buy and Sell Stock II
122
这道和上一道题的唯一区别就是允许多次买卖。总的策略就是买涨~~一直买买卖。
以下代码是我写的。
public int maxProfit(int[] prices) {
if(prices==null||prices.length==0){
return 0;
}
int res = 0;
int buy = prices[0];
for(int i=1;i<prices.length;i++){
if(prices[i]-buy<=0){
buy=prices[i];
}else{
res += prices[i]-buy;
buy=prices[i];
}
}
return res;
}
当我看了官方的解释和代码后，真感觉自己智商被压制了。其实做算法题就是做数学题，关键是找到问题关键。下图就是关键。
image.png
123. 买卖股票的最佳时机 III
利用状态转移方程（动态规划）来解此题。
public int maxProfit(int[] prices) {
if (prices.length == 0) {
return 0;
}
int[] dp = new int[5];
/*
j的5中状态
j=0：不进行任何操作
j=1：第一次买入
j=2：第一次卖出
j=3：第二次买入
j=4：第二次卖出
*/
dp[1] = -prices[0];
dp[3] = Integer.MIN_VALUE;
for (int i = 1; i < prices.length; i++) {
//以下计算为主逻辑，可以考虑将dp声明为一位数组~~
dp[1] = Math.max(dp[1], -prices[i]);
dp[2] = Math.max(dp[2], prices[i] + dp[1]);
dp[3] = Math.max(dp[3], dp[2]-prices[i]);
dp[4] = Math.max(dp[4], prices[i] + dp[3]);
}
return Math.max(0, Math.max(dp[4], dp[2]));
}
