Golang DP 12 ms beats 100%


  • 0
    R
    func maxProfit(prices []int) int {
        n:= len(prices)
        if n < 2 {
            return 0
        }
        k := 2
        if k >= n / 2 {
            len, profit := n, 0
            for i:=1; i < len; i++ {
                if prices[i] > prices[i - 1] {
                    profit += prices[i] - prices[i-1]
                }
            }
            return profit
        }
        
        globalMax := make([][]int, k+1)
        for g := 0; g < k+1; g++ {
            globalMax[g] = make([]int, n)
            for m:=0; m < n; m++ {
                globalMax[g][m] = 0
            }
        }
        
        for i:= 1; i < k + 1; i++ {
            localMax := make([]int, n)
            for a := 0; a < n; a++ {
                localMax[a] = 0
            }
            for j:= 1; j < n; j++ {
                profit:= prices[j] - prices[j-1]
                
                localMax[j] = localMax[j-1] + profit
                if localMax[j] < globalMax[i-1][j-1] + profit {
                    localMax[j] = globalMax[i-1][j-1] + profit
                }
                globalMax[i][j] = localMax[j]
                if globalMax[i][j] < globalMax[i][j-1] {
                    globalMax[i][j] = globalMax[i][j-1]
                }
            }
        }
        return globalMax[k][n-1]
    }
    

Log in to reply
 

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