股票买卖问题

买卖股票的最佳时机相关问题

121. 买卖股票的最佳时机

只能交易一次

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n=prices.size();
        vector<int> dp0(n); //当天不持有股票
        vector<int> dp1(n); //当天持有股票

        //base case
        dp0[0]=0;
        dp1[0]=-prices[0];

        for(int i=1;i<n;i++){
            dp0[i]=max(dp0[i-1], dp1[i-1]+prices[i]);
            dp1[i]=max(dp1[i-1], -prices[i]);
        }
        return dp0[n-1];
    }
};

func maxProfit(prices []int) int {
    n := len(prices)
    dp0 := make([]int, n) //当天不持有股票
    dp1 := make([]int, n) //当天持有股票

    //base case
    dp0[0] = 0
    dp1[0] = -prices[0]

    for i := 1; i < n; i++ {
        dp0[i] = max(dp0[i-1], dp1[i-1]+prices[i])
        dp1[i] = max(dp1[i-1], -prices[i])
    }
    return dp0[n-1]
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

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

交易次数不限

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n=prices.size();
        vector<int> dp0(n); //当天没有持有股票
        vector<int> dp1(n); //当天持有股票

        //base case
        dp0[0]=0;
        dp1[0]=-prices[0];

        for(int i=1;i<n;i++){
            dp0[i]=max(dp0[i-1], dp1[i-1]+prices[i]);
            dp1[i]=max(dp1[i-1], dp0[i-1]-prices[i]);
        }
        return dp0[n-1];
    }
};

func maxProfit(prices []int) int {
    n := len(prices)
    dp0 := make([]int, n) //当天没有持有股票
    dp1 := make([]int, n) //当天持有股票

    //base case
    dp0[0] = 0
    dp1[0] = -prices[0]

    for i := 1; i < n; i++ {
        dp0[i] = max(dp0[i-1], dp1[i-1]+prices[i])
        dp1[i] = max(dp1[i-1], dp0[i-1]-prices[i])
    }
    return dp0[n-1]
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

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

最多交易两次

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n=prices.size();
        vector<vector<int>> dp0(n,vector<int>(3));
        vector<vector<int>> dp1(n,vector<int>(3));

        //base case
        for(int i=1;i<=2;i++){
            dp0[0][i]=0;
            dp1[0][i]=-prices[0];
        }

        for(int i=1;i<n;i++){
            for(int j=2;j>0;j--){
                dp0[i][j]=max(dp0[i-1][j], dp1[i-1][j]+prices[i]);
                dp1[i][j]=max(dp1[i-1][j], dp0[i-1][j-1]-prices[i]);
            }
        }
        return dp0[n-1][2];
    }
};

func maxProfit(prices []int) int {
    n := len(prices)
    dp0 := make([][]int, n)
    dp1 := make([][]int, n)
    for i := 0; i < n; i++ {
        dp0[i] = make([]int, 3)
        dp1[i] = make([]int, 3)
    }

    //base case
    for i := 1; i <= 2; i++ {
        dp0[0][i] = 0
        dp1[0][i] = -prices[0]
    }

    for i := 1; i < n; i++ {
        for j := 2; j > 0; j-- {
            dp0[i][j] = max(dp0[i-1][j], dp1[i-1][j]+prices[i])
            dp1[i][j] = max(dp1[i-1][j], dp0[i-1][j-1]-prices[i])
        }
    }
    return dp0[n-1][2]
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

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

最多可以交易k次

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        int n=prices.size();
        if(n==0) return 0;
        // k = min(n/2, k);
        vector<vector<int>> dp0(n,vector<int>(k+1));
        vector<vector<int>> dp1(n,vector<int>(k+1));

        //base case
        for(int i=1;i<=k;i++){
            dp0[0][i]=0;
            dp1[0][i]=-prices[0];
        }

        for(int i=1;i<n;i++){
            for(int j=k;j>0;j--){
                dp0[i][j]=max(dp0[i-1][j], dp1[i-1][j]+prices[i]);
                dp1[i][j]=max(dp1[i-1][j], dp0[i-1][j-1]-prices[i]);
            }
        }
        return dp0[n-1][k];
    }
};

func maxProfit(k int, prices []int) int {
    n := len(prices)
    if n == 0 {
        return 0
    }
    // k = min(n/2, k)
    dp0 := make([][]int, n)
    dp1 := make([][]int, n)
    for i := 0; i < n; i++ {
        dp0[i] = make([]int, k+1)
        dp1[i] = make([]int, k+1)
    }

    //base case
    for i := 1; i <= k; i++ {
        dp0[0][i] = 0
        dp1[0][i] = -prices[0]
    }

    for i := 1; i < n; i++ {
        for j := k; j > 0; j-- {
            dp0[i][j] = max(dp0[i-1][j], dp1[i-1][j]+prices[i])
            dp1[i][j] = max(dp1[i-1][j], dp0[i-1][j-1]-prices[i])
        }
    }
    return dp0[n-1][k]
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

309.最佳买卖股票时机含冷冻期

交易次数不限，含冷冻期

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

func maxProfit(prices []int) int {
    n := len(prices)
    if n <= 1 {
        return 0
    }
    dp0 := make([]int, n)
    dp1 := make([]int, n)
    
    //base case
    dp0[0] = 0
    dp1[0] = -prices[0]
    dp0[1] = max(dp0[0], dp1[0]+prices[1])
    dp1[1] = max(dp1[0], -prices[1])
    
    for i := 2; i < n; i++ {
        dp0[i] = max(dp0[i-1], dp1[i-1]+prices[i])
        dp1[i] = max(dp1[i-1], dp0[i-2]-prices[i])
    }
    return dp0[n-1]
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

714.买卖股票的最佳时机含手续费

交易次数不限，含手续费

class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        int n=prices.size();
        vector<int> dp0(n);
        vector<int> dp1(n);

        //base case
        dp0[0]=0;
        dp1[0]=-prices[0]-fee;

        for(int i=1;i<n;i++){
            dp0[i]=max(dp0[i-1], dp1[i-1]+prices[i]);
            dp1[i]=max(dp1[i-1], dp0[i-1]-prices[i]-fee);
        }
        return dp0[n-1];
    }
};

func maxProfit(prices []int, fee int) int {
    n := len(prices)
    dp0 := make([]int, n)
    dp1 := make([]int, n)

    //base case
    dp0[0] = 0
    dp1[0] = -prices[0] - fee

    for i := 1; i < n; i++ {
        dp0[i] = max(dp0[i-1], dp1[i-1]+prices[i])
        dp1[i] = max(dp1[i-1], dp0[i-1]-prices[i]-fee)
    }
    return dp0[n-1]
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}