Leetcode股票问题

ゝ一纸荒年。 2022-09-07 09:59 49阅读 0赞

1、股票的最大利润

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

2、买卖股票的最佳时机 II

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

3、买卖股票的最佳时机 III

class Solution {
    public:
        int maxProfit(vector<int>& prices) {
            int n=prices.size();
            if(n<=1) return 0;
     
            int buy1=-prices[0];
            int sell1=0;
            int buy2=-prices[0];
            int sell2=0;
            for(int i=1;i<n;i++) {
                buy1=max(buy1,-prices[i]);
                sell1=max(sell1,buy1+prices[i]);
                buy2=max(buy2,sell1-prices[i]);
                sell2=max(sell2,buy2+prices[i]);
            }
            return sell2;
        }
    };

4、买卖股票的最佳时机 IV

class Solution {
    public:
        int maxProfit(int k, vector<int>& prices) {
            int n=prices.size();
            if(n<=1) return 0;
            vector<vector<int>> v(k+1,vector<int>(n,0));
     
            int maxs=INT_MIN;
            for(int i=1;i<=k;i++) {
                maxs=INT_MIN;
                for(int j=1;j<n;j++) {
                    //完成第j笔交易，必须先买
                    maxs=max(maxs,v[i-1][j-1]-prices[j-1]);
                    //不操盘或者卖出
                    v[i][j]=max(v[i][j-1],maxs+prices[j]);
                }
            }
            return v[k][n-1];
        }
    };

5、最佳买卖股票时机含冷冻期

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

6、[买卖股票的最佳时机含手续费][Link 1]

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

[Link 1]: https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/