Leetcode - Best Time to Buy and Sell Stock

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 * 动态规划： dp[i] = max(dp[i-1],prices[i]-prices[j])
 */
fun maxProfit(prices: Array<Int>): Int {
    /** 记录全局最大利润 */
    var maxProfit = 0;
    /** 记录全局最小交易金额 */
    var minPrice = Int.MAX_VALUE
    for (price in prices) {
        /** 找出最小值 */
        minPrice = min(minPrice, price)
        /** 最大利润：当前最大利润 OR 当前金额-最小交易金额 */
        maxProfit = max(maxProfit, price - minPrice)
    }
    return maxProfit
}
maxProfit(arrayOf(7,6,4,3,1))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * 上图所示 C < A + B
 * A + B 的利润是最多的
 */
fun maxProfit21(prices: IntArray): Int {
    var maxProfit = 0
    var i = 0
    while (i < prices.size - 1) {
        while (i < prices.size - 1 && prices[i] > prices[i + 1]) {
            i++
        }
        val valley = prices[i]
        while (i < prices.size - 1 && prices[i] <= prices[i + 1]) {
            i++
        }
        val peak = prices[i]
        
        maxProfit += peak - valley
    }
    return maxProfit
}

1
2
3
4
5
6
7
8
9
10
11
12
/**
 * 上图所示 D = A + B + C
 */
fun maxProfit2(prices: IntArray): Int {
    var maxProfit = 0
    for (i in 1 until prices.size) {
        if (prices[i] > prices[i - 1]) {
            maxProfit += prices[i] - prices[i - 1]
        }
    }
    return maxProfit
}