给定一个正数数组arr(即数组元素全是正数),找出该数组中,两个元素相减的最大值,其中被减数的下标不小于减数的下标。即求出: maxValue = max{arr[j]-arr[i] and j >= i}?
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
}
执行结果如下: