2021-07-05：股票问题2。给定一个数组 prices ，其中 prices[i] 是一支给定股票第 i 天的价格。设计一

福大大架构师每日一题

发布于 2021-08-05 16:16:59

4830

发布于 2021-08-05 16:16:59

2021-07-05：股票问题2。给定一个数组 prices ，其中 prices[i] 是一支给定股票第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

福大大答案2021-07-05：

一次遍历法。

遍历的时候，累加所有的大于0的【prices[i]-prices[i-1]】，这个累加值就是需要返回的值。

时间复杂度：O(N)。空间复杂度：O(1)。

代码用golang编写。代码如下：

package main

import "fmt"

func main() {
    arr := []int{7, 1, 5, 3, 6, 4}
    ret := maxProfit(arr)
    fmt.Println(ret)
}

func maxProfit(prices []int) int {
    N := len(prices)
    if N <= 1 {
        return 0
    }
    ans := 0
    for i := 1; i < N; i++ {
        ans += getMax(prices[i]-prices[i-1], 0)
    }
    return ans
}

func getMax(a int, b int) int {
    if a > b {
        return a
    } else {
        return b
    }
}

执行结果如下：