funcmaxProfit(prices []int) int { Max,Min :=0,math.MaxIntfor _,v :=range prices { Max =max(Max,v-Min) Min =min(Min,v) }return Max}funcmin(a, b int) int {if a < b {return a }return b}funcmax(a, b int) int {if a > b {return a }return b}
思路二
动态规划
解题方法
dp[i] 代表前 i 天获取的最大利润,则 dp[i]=max(dp[i-1],prices[i]-min)
复杂度
时间复杂度:O(n)
空间复杂度:O(n)
funcmaxProfit(prices []int) int { length :=len(prices)if length ==0 {return0 } dp :=make([]int,length) Min := prices[0]for i:=1;i<length;i++{ Min =min(Min,prices[i]) dp[i]=max(dp[i-1],prices[i]-Min) }return dp[length-1]}funcmin(a, b int) int {if a < b {return a }return b}funcmax(a, b int) int {if a > b {return a }return b}