php 解法, 执行用时: 64 ms, 内存消耗: 64.3 MB, 提交时间: 2023-10-04 09:01:51

class Solution {

    /**
     * @param Integer $k
     * @param Integer[] $prices
     * @return Integer
     */
    public function maxProfit($k, $prices) {
        if (empty($prices) || $k <= 0) return 0;

        // 交易次数过大，导致内存溢出。这里认为$k超过天数的一半就认为交易次数不限了，走买卖股票的最佳时机 II这个逻辑
        if ($k > (count($prices) / 2)) return $this->maxProfitInf($prices);

        $dp = [];

        for ($i = 0; $i < count($prices); $i++) {
            for ($j = $k; $j >= 1; $j--) {
                if ($i == 0) {
                    $dp[$i][$j][0] = 0;
                    $dp[$i][$j][1] = -$prices[$i];
                    continue;
                }
                $dp[$i][$j][0] = max($dp[$i - 1][$j][0], $dp[$i - 1][$j][1] + $prices[$i]);
                $dp[$i][$j][1] = max($dp[$i - 1][$j][1], $dp[$i - 1][$j - 1][0] - $prices[$i]);
            }
        }

        return $dp[count($prices) - 1][$k][0];
    }

    // 买卖股票，尽可能多的完成交易
    public function maxProfitInf($prices) {
        if (empty($prices)) return 0;

        $dp = [];

        $dp[0][0] = 0;
        $dp[0][1] = -$prices[0];
        for ($i = 1; $i < count($prices); $i++) {
            $dp[$i][0] = max($dp[$i - 1][0], $dp[$i - 1][1] + $prices[$i]);
            $dp[$i][1] = max($dp[$i - 1][0] - $prices[$i], $dp[$i - 1][1]);
        }

        return $dp[count($prices) - 1][0];
    }
}

javascript 解法, 执行用时: 92 ms, 内存消耗: 45.1 MB, 提交时间: 2023-10-04 09:00:44

/**
 * @param {number} k
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(k, prices) {
    if (!prices.length) {
        return 0;
    }

    const n = prices.length;
    k = Math.min(k, Math.floor(n / 2));
    const buy = new Array(n).fill(0).map(() => new Array(k + 1).fill(0));
    const sell = new Array(n).fill(0).map(() => new Array(k + 1).fill(0));

    buy[0][0] = -prices[0];
    sell[0][0] = 0;
    for (let i = 1; i <= k; ++i) {
        buy[0][i] = sell[0][i] = -Number.MAX_VALUE;
    }

    for (let i = 1; i < n; ++i) {
        buy[i][0] = Math.max(buy[i - 1][0], sell[i - 1][0] - prices[i]);
        for (let j = 1; j <= k; ++j) {
            buy[i][j] = Math.max(buy[i - 1][j], sell[i - 1][j] - prices[i]);
            sell[i][j] = Math.max(sell[i - 1][j], buy[i - 1][j - 1] + prices[i]);   
        }
    }

    return Math.max(...sell[n - 1]);
};

var maxProfit2 = function(k, prices) {
    if (!prices.length) {
        return 0;
    }

    const n = prices.length;
    k = Math.min(k, Math.floor(n / 2));
    const buy = new Array(k + 1).fill(0);
    const sell = new Array(k + 1).fill(0);

    [buy[0], sell[0]] = [-prices[0], 0]
    for (let i = 1; i < k + 1; ++i) {
        buy[i] = sell[i] = -Number.MAX_VALUE;
    }

    for (let i = 1; i < n; ++i) {
        buy[0] = Math.max(buy[0], sell[0] - prices[i]);
        for (let j = 1; j < k + 1; ++j) {
            buy[j] = Math.max(buy[j], sell[j] - prices[i]);
            sell[j] = Math.max(sell[j], buy[j - 1] + prices[i]); 
        }
    }

    return Math.max(...sell)
};

cpp 解法, 执行用时: 8 ms, 内存消耗: 14.1 MB, 提交时间: 2023-10-04 09:00:01

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        if (prices.empty()) {
            return 0;
        }

        int n = prices.size();
        k = min(k, n / 2);
        vector<vector<int>> buy(n, vector<int>(k + 1));
        vector<vector<int>> sell(n, vector<int>(k + 1));

        buy[0][0] = -prices[0];
        sell[0][0] = 0;
        for (int i = 1; i <= k; ++i) {
            buy[0][i] = sell[0][i] = INT_MIN / 2;
        }

        for (int i = 1; i < n; ++i) {
            buy[i][0] = max(buy[i - 1][0], sell[i - 1][0] - prices[i]);
            for (int j = 1; j <= k; ++j) {
                buy[i][j] = max(buy[i - 1][j], sell[i - 1][j] - prices[i]);
                sell[i][j] = max(sell[i - 1][j], buy[i - 1][j - 1] + prices[i]);   
            }
        }

        return *max_element(sell[n - 1].begin(), sell[n - 1].end());
    }
    
    // 2. 
    int maxProfit2(int k, vector<int>& prices) {
        if (prices.empty()) {
            return 0;
        }

        int n = prices.size();
        k = min(k, n / 2);
        vector<int> buy(k + 1);
        vector<int> sell(k + 1);

        buy[0] = -prices[0];
        sell[0] = 0;
        for (int i = 1; i <= k; ++i) {
            buy[i] = sell[i] = INT_MIN / 2;
        }

        for (int i = 1; i < n; ++i) {
            buy[0] = max(buy[0], sell[0] - prices[i]);
            for (int j = 1; j <= k; ++j) {
                buy[j] = max(buy[j], sell[j] - prices[i]);
                sell[j] = max(sell[j], buy[j - 1] + prices[i]);   
            }
        }

        return *max_element(sell.begin(), sell.end());
    }
};

java 解法, 执行用时: 3 ms, 内存消耗: 39.4 MB, 提交时间: 2023-08-18 15:46:16

class Solution {
    public int maxProfit(int k, int[] prices) {
        if (prices.length == 0) {
            return 0;
        }

        int n = prices.length;
        k = Math.min(k, n / 2);
        int[] buy = new int[k + 1];
        int[] sell = new int[k + 1];

        buy[0] = -prices[0];
        sell[0] = 0;
        for (int i = 1; i <= k; ++i) {
            buy[i] = sell[i] = Integer.MIN_VALUE / 2;
        }

        for (int i = 1; i < n; ++i) {
            buy[0] = Math.max(buy[0], sell[0] - prices[i]);
            for (int j = 1; j <= k; ++j) {
                buy[j] = Math.max(buy[j], sell[j] - prices[i]);
                sell[j] = Math.max(sell[j], buy[j - 1] + prices[i]);   
            }
        }

        return Arrays.stream(sell).max().getAsInt();
    }
}

golang 解法, 执行用时: 4 ms, 内存消耗: 2.1 MB, 提交时间: 2023-08-18 15:45:52

func maxProfit(k int, prices []int) int {
    n := len(prices)
    if n == 0 {
        return 0
    }

    k = min(k, n/2)
    buy := make([]int, k+1)
    sell := make([]int, k+1)
    buy[0] = -prices[0]
    for i := 1; i <= k; i++ {
        buy[i] = math.MinInt64 / 2
        sell[i] = math.MinInt64 / 2
    }

    for i := 1; i < n; i++ {
        buy[0] = max(buy[0], sell[0]-prices[i])
        for j := 1; j <= k; j++ {
            buy[j] = max(buy[j], sell[j]-prices[i])
            sell[j] = max(sell[j], buy[j-1]+prices[i])
        }
    }
    return max(sell...)
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

func max(a ...int) int {
    res := a[0]
    for _, v := range a[1:] {
        if v > res {
            res = v
        }
    }
    return res
}

python3 解法, 执行用时: 120 ms, 内存消耗: 16.1 MB, 提交时间: 2023-08-18 15:45:35

class Solution:
    def maxProfit(self, k: int, prices: List[int]) -> int:
        if not prices:
            return 0

        n = len(prices)
        k = min(k, n // 2)
        buy = [0] * (k + 1)
        sell = [0] * (k + 1)

        buy[0], sell[0] = -prices[0], 0
        for i in range(1, k + 1):
            buy[i] = sell[i] = float("-inf")

        for i in range(1, n):
            buy[0] = max(buy[0], sell[0] - prices[i])
            for j in range(1, k + 1):
                buy[j] = max(buy[j], sell[j] - prices[i])
                sell[j] = max(sell[j], buy[j - 1] + prices[i]); 

        return max(sell)

python3 解法, 执行用时: 44 ms, 内存消耗: 16.1 MB, 提交时间: 2023-08-18 15:44:57

class Solution:
    def maxProfit(self, k: int, prices: List[int]) -> int:
        if not prices:
            return 0

        n = len(prices)
        # 二分查找的上下界
        left, right = 1, max(prices)
        # 存储答案，如果值为 -1 表示二分查找失败
        ans = -1

        while left <= right:
            # 二分得到当前的斜率（手续费）
            c = (left + right) // 2

            # 使用与 714 题相同的动态规划方法求解出最大收益以及对应的交易次数
            buyCount = sellCount = 0
            buy, sell = -prices[0], 0

            for i in range(1, n):
                if sell - prices[i] >= buy:
                    buy = sell - prices[i]
                    buyCount = sellCount
                if buy + prices[i] - c >= sell:
                    sell = buy + prices[i] - c
                    sellCount = buyCount + 1

            # 如果交易次数大于等于 k，那么可以更新答案
            # 这里即使交易次数严格大于 k，更新答案也没有关系，因为总能二分到等于 k 的
            if sellCount >= k:
                # 别忘了加上 kc
                ans = sell + k * c
                left = c + 1
            else:
                right = c - 1

        # 如果二分查找失败，说明交易次数的限制不是瓶颈
        # 可以看作交易次数无限，直接使用贪心方法得到答案
        if ans == -1:
            ans = sum(max(prices[i] - prices[i - 1], 0) for i in range(1, n))

        return ans