Best Time to Buy and Sell Stock IV

algorithm
dp, algorithm

Description

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most k transactions.

Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

Recursion formula

Recursion code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func maxProfit(k int, prices []int) int {
    if k == 0 {
        return 0
    }
    if len(prices) == 0 || len(prices) == 1 {
        return 0
    }
    tmpMax := 0
    for i := 0; i < len(prices) - 1; i ++ {
        tmpMax = max(tmpMax, maxProfit(k-1, prices[:i]) + prices[len(prices)-1] - prices[i]
        }
    }
    return max(maxProfit(k, prices[:len(prices)-1]), tmpMax)
}
func max(a int, b int) int {
    if a >= b {
        return a
    } else {
        return b
    }
}

A little optimize

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func maxProfit(k int, prices []int) int {
    if k == 0 {
        return 0
    }
    if len(prices) == 0 || len(prices) == 1 {
        return 0
    }
    tmpMax := 0
    for i := 0; i < len(prices) - 1; i ++ {
        if prices[len(prices)-1] > prices[i] {
            tmpMax = max(tmpMax, maxProfit(k-1, prices[:i]) + prices[len(prices)-1] - prices[i])
        }
    }
    return max(maxProfit(k, prices[:len(prices)-1]), tmpMax)
}
func max(a int, b int) int {
    if a >= b {
        return a
    } else {
        return b
    }
}

Non recursion solution

1
2
Comentarios