188. Best Time to Buy and Sell Stock IV
你有一個整數數組 prices，其中 prices[i] 是第 i 天某支股票的價格，還有一個整數 k。
找出你能達到的最大利潤。你最多可以完成 k 筆交易：即你最多可以買 k 次和賣 k 次。
注意：你不能同時進行多筆交易（即，你必須在再次購買之前賣掉股票）。
範例：
輸入：k = 2, prices = [2,4,1]
輸出：2 解釋：在第 1 天（價格 = 2）買入，在第 2 天（價格 = 4）賣出，利潤 = 4-2 = 2。
Python
from typing import List
class Solution:
def maxProfit(self, k: int, prices: List[int]) -> int:
# If there are no prices or k is 0, profit is 0
if not prices or k == 0:
return 0
n = len(prices)
# If k is greater than half the length of prices, it's equivalent to unlimited transactions
if k >= n // 2:
return self.maxProfitUnlimited(prices)
# Initialize dp array
dp = [[0] * (k + 1) for _ in range(n)]
# Iterate over each transaction
for j in range(1, k + 1):
maxDiff = -prices[0]
for i in range(1, n):
dp[i][j] = max(dp[i-1][j], prices[i] + maxDiff)
maxDiff = max(maxDiff, dp[i-1][j-1] - prices[i])
return dp[-1][-1]
def maxProfitUnlimited(self, prices: List[int]) -> int:
# Function to calculate maximum profit with unlimited transactions
profit = 0
for i in range(1, len(prices)):
if prices[i] > prices[i-1]:
profit += prices[i] - prices[i-1]
return profit
17.07MB, 97ms
C++
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
int maxProfit(int k, vector<int>& prices) {
// If there are no prices or k is 0, profit is 0
if (prices.empty() || k == 0) {
return 0;
}
int n = prices.size();
// If k is greater than half the length of prices, it's equivalent to unlimited transactions
if (k >= n / 2) {
return maxProfitUnlimited(prices);
}
// Initialize dp array
vector<vector<int>> dp(n, vector<int>(k + 1, 0));
// Iterate over each transaction
for (int j = 1; j <= k; ++j) {
int maxDiff = -prices[0];
for (int i = 1; i < n; ++i) {
dp[i][j] = max(dp[i-1][j], prices[i] + maxDiff);
maxDiff = max(maxDiff, dp[i-1][j-1] - prices[i]);
}
}
return dp[n-1][k];
}
private:
int maxProfitUnlimited(const vector<int>& prices) {
// Function to calculate maximum profit with unlimited transactions
int profit = 0;
for (size_t i = 1; i < prices.size(); ++i) {
if (prices[i] > prices[i-1]) {
profit += prices[i] - prices[i-1];
}
}
return profit;
}
};
14.88MB, 6ms
Javascript
/**
* @param {number} k
* @param {number[]} prices
* @return {number}
*/
var maxProfit = function(k, prices) {
// If there are no prices or k is 0, profit is 0
if (prices.length === 0 || k === 0) {
return 0;
}
const n = prices.length;
// If k is greater than half the length of prices, it's equivalent to unlimited transactions
if (k >= Math.floor(n / 2)) {
return maxProfitUnlimited(prices);
}
// Initialize dp array
const dp = Array.from({ length: n }, () => Array(k + 1).fill(0));
// Iterate over each transaction
for (let j = 1; j <= k; j++) {
let maxDiff = -prices[0];
for (let i = 1; i < n; i++) {
dp[i][j] = Math.max(dp[i-1][j], prices[i] + maxDiff);
maxDiff = Math.max(maxDiff, dp[i-1][j-1] - prices[i]);
}
}
return dp[n-1][k];
};
// Function to calculate maximum profit with unlimited transactions
function maxProfitUnlimited(prices) {
let profit = 0;
for (let i = 1; i < prices.length; i++) {
if (prices[i] > prices[i-1]) {
profit += prices[i] - prices[i-1];
}
}
return profit;
}
51.57MB, 71ms
