Leetcode Best Time to Buy and Sell Stock IV problem solution

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.

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];
}