当前位置 博文首页 > zhouyu的博客:LeetCode题解第122题
122题.买卖股票的最佳时机
1、思路:如果第二天的售价大于当天的售价则当天买入第二天卖出,这样算的话可能出现当天卖出又买入的情况,所以不是实际的买入和卖出过程,仅仅是为了算出最大利润而采用的方法。
class Solution {
public int maxProfit(int[] prices) {
int count = 0;
for(int i = 0; i < prices.length - 1; i++){
if(prices[i + 1] > prices[i]){ //如果有利可图则进行买卖操作
count += prices[i + 1] - prices[i];
}
}
return count;
}
}
2、思路:考虑每天结束时的两种状态,持有股票和不持有股票,而这两种状态到当天的最大利润仅于前一天的两种状态的利润有关。
1)在当天结束持有股票时,分为两种情况,股票是当天买的,则此时利润为前一天不持有股票的利润去掉当天股票的价格,或者股票不是当前买的,则此时利润为前一天持有股票的利润,在二者选大的,则为当天结束持有股票的最大利润
2)在当天结束不持有股票也分为两种情况,股票是当天卖出的,则此时利润为前一天持有股票的利润加上当天股票的价格,或者股票不是当天卖出的,则此时利润为前一天不持有股票的利润,在二者选大的,则为当天结束不持有股票的最大利润
可知,全部交易后,不持有股票的利润肯定大于持有股票的利润,则最后返回不持有股票的最大利润即为答案
class Solution {
public int maxProfit(int[] prices) {
int none = 0;//定义初始状态,不持有股票利润为0
int have = -prices[0];//持有股票利润为负的第一天的售价
for(int i = 1; i < prices.length; i++){
//利用临时变量存储当天两种状态可获得的最大利润
int none1 = none > have + prices[i]?none:have+prices[i];
int have1 = have > none - prices[i]?have:none - prices[i];
none = none1;
have = have1;
}
return none;
}
}
cs