2020-10-30：給定一個正數(shù)數(shù)組arr（即數(shù)組元素全是正數(shù)）淤堵，找出該數(shù)組中寝衫，兩個元素相減的最大值，其中被減數(shù)的下標(biāo)不小于減數(shù)的下標(biāo)拐邪。即求出： maxValue = max{arr[j]-arr[i] and j >= i}慰毅？
福哥答案2020-10-30：
1.雙重遍歷法。
2.一次遍歷法扎阶。
golang代碼如下：
package main
import "fmt"
const INT_MAX = int(^uint(0) >> 1)
func main() {
s := []int{7, 1, 5, 3, 6, 4}
fmt.Println("雙重遍歷法：", MaxProfit2(s))
fmt.Println("一次遍歷法：", MaxProfit1(s))
}
//雙重遍歷法
func MaxProfit2(prices []int) int {
maxprofit := 0
for i := 0; i < len(prices); i++ {
for j := i + 1; j < len(prices); j++ {
profit := prices[j] - prices[i]
if profit > maxprofit {
maxprofit = profit
}
}
}
return maxprofit
}
//一次遍歷法
func MaxProfit1(prices []int) int {
minprice := INT_MAX
maxprofit := 0
for i := 0; i < len(prices); i++ {
if prices[i] < minprice {
minprice = prices[i]
} else if prices[i]-minprice > maxprofit {
maxprofit = prices[i] - minprice
}
}
return maxprofit
}
執(zhí)行結(jié)果如下：
image.png
