leetcode-Best Time to Buy and Sell Stock

Best Time to Buy and Sell Stock

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if(prices.size()==0) return 0;
        int min = prices[0];
        int res=0;
        for(int i=1;i<prices.size();i++){
            if(prices[i]<min) {
                min = prices[i];
            }
            else{
                if(res<prices[i]-min) res =prices[i]-min;
            }
        }
        return res;
    }
};

其实也算是DP，每次的结果和前一次的结果比较

Best Time to Buy and Sell Stock II


class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if(prices.size()==0) return 0;
        int profit = 0;
        int min = prices[0];
        int max = prices[0];
        for(int i=1;i<prices.size();i++){
            if(prices[i]<prices[i-1]){
                profit+=max-min;
                min = prices[i];
                max = prices[i];
            }
            else{
                max = max>prices[i]?max:prices[i];
            }
        }
        profit+=max-min;
        return profit;
    }
};

每次下跌前将之前的股票卖出以获得最高的总额

Best Time to Buy and Sell Stock III

DP1

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if(prices.size()==0) return 0;
        vector<int> profit1(prices.size(), 0);
        vector<int> profit2(prices.size(), 0);
        int min = prices[0];
        int maxp = 0;
        for(int i=1;i<prices.size();i++){
            if(prices[i]<min){
                min = prices[i];
                profit1[i] = maxp;
            }
            else {
                if(prices[i]-min>maxp) maxp = prices[i]-min;
                profit1[i] = maxp;
            }
        }
        for(int i=1;i<prices.size();i++){
            int temp = 0;
            for(int j=1;j<i;j++){
                temp = max(temp, prices[i]-prices[j]+profit1[j]);
            }
            profit2[i] = max(temp, profit1[i]);
        }
        int profit = 0;
        for(int i=0;i<profit1.size();i++) cout<<profit1[i];
        cout<<endl;
        for(int i=0;i<prices.size();i++){
            if(profit2[i]>profit) profit = profit2[i];
            cout<<profit2[i];
        }
        cout<<endl;
        return profit;
    }
};

Simplest DP concept. For everyday, there are 3 choices: buy nothing(0) / buy and sell one stock/ buy and sell two stocks. Buy and sell one stock can be calculated by one pass as in series I. Buy and sell two stocks the profit and be divided into the best one stock profit in Day j and best profit between Day j and Day i. i.e. prices[i]-prices[j]+profit1[j] The best profit must comes from a day with minimum price, then that day's profit1 cannot exceed previous day's profit. Here profit1 should be the best profit from 1 stock till now.
Then profit2[i] is max(max(prices[i]-prices[j]+profit1[j]), profit1[i]).

DP2
Consider to improve DP1, find that max(prices[i]-prices[j]+profit1[j]) can be simplified to prices[1]+max(profit1[j]-prices[j]), thus we have no need to calculate profit1[j]-prices[j] every i, just calculate max of it for every j once. O(n2)->O(n)

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if(prices.size()==0) return 0;
        vector<int> profit1(prices.size(), 0);
        vector<int> profit2(prices.size(), 0);
        int min = prices[0];
        int maxp = 0;
        for(int i=1;i<prices.size();i++){
            if(prices[i]<min){
                min = prices[i];
                profit1[i] = maxp;
            }
            else {
                if(prices[i]-min>maxp) maxp = prices[i]-min;
                profit1[i] = maxp;
            }
        }
        vector<int> maxp1(prices.size(),0);
        maxp1[0]=profit1[0]-prices[0];
        for(int i=1;i<maxp1.size();i++){
            maxp1[i] = max(maxp1[i-1], profit1[i]-prices[i]);
        }
        //for(int i=0;i<profit1.size();i++) cout<<profit1[i];
       // cout<<endl;
        //for(int i=0;i<profit1.size();i++) cout<<maxp1[i];
        //cout<<endl;
        for(int i=1;i<prices.size();i++){
            profit2[i] = max(maxp1[i-1]+prices[i], profit1[i]);
        }
        int profit = 0;
        for(int i=0;i<prices.size();i++){
            if(profit2[i]>profit) profit = profit2[i];
            //cout<<profit2[i];
        }
        //cout<<endl;
        return profit;
    }
};

DP3
Find that profit2 only depends on maxp and profit1 before it, so can improve O(n) space to O(1).

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if(prices.size()==0) return 0;
        int profit1=0;
        int maxp1=-prices[0];
        int profit2=0;
        int min = prices[0];
        for(int i=1;i<prices.size();i++){
            if(prices[i]<min){
                min = prices[i];
            }
            else {
                if(prices[i]-min>profit1) profit1 = prices[i]-min;
            }
            profit2 = max(profit2, profit1);
            profit2 = max(profit2, maxp1+prices[i]);
            maxp1=max(maxp1, profit1-prices[i]);
        }
        return profit2;
    }
};

还有一种方法是以第i天为中线，计算0-i的股票最大收益+i-end的股票最大收益。
一开始认为对每个i都需要计算0-i和i-end需要O（n2）time，但是实际上只需要对每一天j计算股票0-j的收益，和j-end的收益，计算好之后再以i分隔，时间为O（n）。

Best Time to Buy and Sell Stock IV

依照之前的DP，复杂度为O（kn），k过大的情况下会TLE

单独考虑K大的情况，K>n/2则所有增益都能获得
不考虑每天的买入买出只考虑上涨的pair，之后有空再补

Best Time to Buy and Sell Stock with Cooldown

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if(prices.size()<=1) return 0;
        vector<int> buy(prices.size(), 0);
        vector<int> sell(prices.size(), 0);
        buy[0] = -prices[0];
        buy[1] = max(-prices[1], -prices[0]);
        sell[0] = 0;
        sell[1] = prices[1]-prices[0]>0?prices[1]-prices[0]:0;
        for(int i=2;i<prices.size();i++){
            buy[i] = max(buy[i-1], sell[i-2] - prices[i]);
            sell[i] = max(sell[i-1], buy[i-1]+prices[i]);
        }
        return sell[sell.size()-1];
    }
};

最后编辑于：2019.07.30 16:46:11