LeetCode 买卖股票的最佳时机 （动态规划）

121. 买卖股票的最佳时机

 

class Solution {
public:
    int maxProfit(vector<int>& a) {
        int n = a.size();
        if(!n)return 0;
        
        int _min = a[0];
        int ans = INT_MIN;
        for(int i = 1;i<n;++i){
            ans = max(ans,a[i] - _min);
            _min = min(_min,a[i]);
        }
        return ans>0?ans:0;
        
    }
};

 

 

 

 

 

122. 买卖股票的最佳时机 II

 

 

emmm，这个画图感受一下吧，正因为有序，所以可以直接相邻直接贪心。

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

 

 

123. 买卖股票的最佳时机 III

分析：最多可以买卖两次。

可以设置四个状态，b1代表第一次买最省，b2代表第二次买最省，s1代表第一次买赚的最多，s2代表第二次买最省。

然后从前到后更新上面四个状态就行了。

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int b1=INT_MIN,b2=INT_MIN;
        int s1=0,s2=0;
        for(int i=0;i<prices.size();i++)
        {
            b1=max(b1,-prices[i]);
            s1=max(s1,b1+prices[i]);
            b2=max(b2,s1-prices[i]);
            s2=max(s2,b2+prices[i]);
        }
        return s2;
    }
};

 

 

188. 买卖股票的最佳时机 IV

 

 

 

和上面的题类似，不过可以优化一下，当k>n/2的时候，就相当于不限次数了。

class Solution {
public:
    int maxProfit(int k, vector<int>& a) {
        int n = a.size();
        if(!n || !k)return 0;
        if(k>=n/2){//不限次数
             int n = a.size();
             int ans = 0;
            for(int i = 1;i<n;++i)
                if(a[i] > a[i-1])ans += a[i] - a[i-1];
             return ans;
        }
        vector<long long> b(k+2,-1e11);
        vector<long long> s(k+2,0);
        
        for(int i = 0;i<n;++i){
             b[1] = max(b[1],-1ll*a[i]);
             s[1] = max(s[1],b[1] + a[i]);
             for(int j = 2;j<=k;++j){
                 b[j] = max(b[j],s[j-1]-a[i]);
                 s[j] = max(s[j],b[j] + a[i]);
                
             }       
        }
        return s[k];
    
    }
};