3ms JAVA beat 97%


  • 0
    A

    I follow the "Best Time to Buy and Sell Stock III" top one solution way to do this. And get accpected.

    public int maxProfit(int k, int[] prices) {
    
        if(prices == null || prices.length < 2 || k == 0) return 0;
        if(k >= prices.length / 2){
            return greedy(prices);
        }
        int[] buy = new int[k];
        int[] sell = new int[k];
        for(int i = 0; i < k; i++){
            buy[i] = Integer.MIN_VALUE;
        }
        for(int price: prices){
            for(int i = 0; i < k; i++){
                if(i == 0){
                    if(buy[i] < -price) buy[i] = -price;
                }
                else{
                    if(buy[i] < sell[i - 1] - price) buy[i] = sell[i - 1] - price;
                }
                if(sell[i] < buy[i] + price) sell[i] = buy[i] + price;
            }
        }
        return sell[k - 1];
    }
    public int greedy(int[] prices){
        int num = 0;
        for(int i = 1; i < prices.length; i++){
            if(prices[i] > prices[i - 1]) num += prices[i] - prices[i - 1];
        }
        return num;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.