In this Leetcode Best Time to Buy and Sell Stock IV problem solution, You are given an integer array price where prices[i] is the price of a given stock on an ith day and an integer k. Find the maximum profit you can achieve. You may complete most k transactions.

Leetcode Best Time to Buy and Sell Stock IV problem solution


Problem solution in Python.

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

        if k == 0 or len(prices) == 0:
            return 0

        min_price, profit = [float('inf')] * k, [float('-inf')] * k
        for price in prices:
            min_price[0] = min(min_price[0], price)
            profit[0] = max(profit[0], price - min_price[0])
            for i in range(1, k):
                min_price[i] = min(min_price[i], price - profit[i-1])
                profit[i] = max(profit[i], price - min_price[i])
        
        return profit[k-1]



Problem solution in Java.

class Solution {
    public int maxProfit(int k, int[] prices) {
        if(k==0 || prices.length==0)
            return 0;
        
        int[] cost = new int[k];
        int[] profits = new int[k];
        
        Arrays.fill(cost, Integer.MAX_VALUE);
        Arrays.fill(profits, 0);
        
        for(int price: prices){
            for(int i=0; i<k; i++){
                if(i==0){// first time buy the stock 
                    cost[i] = Math.min(cost[i], price);
                    profits[i] = Math.max(profits[i], price - cost[i] );
                }else{// from 2nd time to k times we should buy from previous profits
                    cost[i] = Math.min(cost[i], price - profits[i-1]);
                    profits[i] = Math.max(profits[i], price - cost[i] );
                }
            }   
        }    
        
        return profits[k-1];
    }
}


Problem solution in C++.

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        int n=prices.size();
        if(n==0){
            return 0;
        }
        int dp[k+1][n];
        
        for(int t=0;t<=k;t++){
            for(int d=0;d<n;d++){
                dp[t][d]=0;
            }
        }
        
        for(int t=1;t<=k;t++){
            int ans=INT_MIN;
            for(int d=1;d<n;d++){
                ans=max(ans,dp[t-1][d-1]-prices[d-1]);
                dp[t][d]=max(dp[t][d-1],ans+prices[d]);
            }
        }
        
        return dp[k][n-1];
    }
};


Problem solution in C.

int max(int a, int b)
{
    return a > b ? a : b;
}

int maxProfit2(int* prices, int pricesSize)
{
    if(pricesSize == 1)
    {
        return 0;
    }
    
    int maxprofit = 0;
    
    for(int i = 1; i < pricesSize; ++i)
    {
        if(prices[i] - prices[i-1] > 0)
        {
            maxprofit = maxprofit + prices[i] - prices[i-1];
        }
    }
    
    return maxprofit;
}

int maxProfit(int k, int* prices, int pricesSize)
{
    if(pricesSize == 0)
    {
        return 0;
    }
    
    if(k > pricesSize)
    {
        return maxProfit2(prices, pricesSize);
    }
    
    int* global = (int*)malloc(sizeof(int) * (k+1));
    int* local = (int*)malloc(sizeof(int) * (k+1));
    
    for(int i = 0; i < k + 1; ++i)
    {
        global[i] = 0;
        local[i] = 0;
    }
    
    for(int i = 0; i < pricesSize - 1; ++i)
    {
        int diff = prices[i+1] - prices[i];
        
        for(int j = k; j >= 1; --j)
        {
            local[j] = max(global[j-1] + max(diff, 0), local[j] + diff);
            global[j] = max(global[j], local[j]);
        }
    }
    
    return global[k];
}