leetcode 122 买卖股票的最佳时机

佚名 6年前 (2019-04-09) 随笔 1916人围观抢沙发百度已收录

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

先贴个丑代码：这个代码避开了重复交易的陷阱，但是依然很丑：

int res=0;
        int len=prices.size();
        if(len<2) return res;
        for(int i=0;i<len-1;i++){
            int a=0,b=0;
            if(prices[i+1]-prices[i]>=0){
                a=i;
                int j=0;
                while(i+j<len-1){
                    if(prices[i+j+1]-prices[i+j]<=0){
                        b=i+j;break;
                    }else if(i+j+1==len-1){
                        b=i+j+1;
                    }
                    j++;
                }
                i+=j;
                if(prices[b]-prices[a]>0) res+=prices[b]-prices[a];
                //cout<<"a "<<a<<"b "<<b<<endl;
            }
        }
        return res;

贪心算法：如果今天买明天能够盈利，那就今天买入明天卖出；对于这个问题来讲是具有最优子结构性质的

分情况：

1）当len<1；不会赚钱，return 0；

2）

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        //贪心算法
        int res=0;
        int len=prices.size();
        if(len<1) return 0;
        for(int i=1;i<len;i++){
            if(prices[i]-prices[i-1]>0)
                res+=prices[i]-prices[i-1];
        }
        return res;
    }
};