一个小的算法题目
一排树中,每棵树上都有若干虫子,用一个数组表示。
消杀可以杀灭其中一棵树上的所有虫子,但相邻的两棵树上的虫子会飞走(不会落回到某棵树上)。
为了消灭最多的虫子,写一种算法选择出应该消杀哪些棵树,并求出能消灭的虫子数量。
实现
https://github.com/zongzw-learn/learn-go/tree/master/code-test/max-indvidials
package main
import "log"
func main() {
a := []int{2, 3, 5, 4, 1, 4} // 0 2 5
x, y := maxab(a, 0)
log.Printf("max: %d, %v", x, y)
}
func maxab(a []int, o int) (int, []int) {
if len(a) == 1 {
return a[0], []int{o}
}
if len(a) == 2 {
if a[0] > a[1] {
return a[0], []int{o}
} else {
return a[1], []int{1 + o}
}
}
x1, y1 := maxab(a[2:], 2+o)
x2, y2 := maxab(a[1:], 1+o)
if a[0]+x1 > x2 {
return a[0] + x1, append([]int{o}, y1...)
} else {
return x2, y2
}
}
标签:return,int,问题,虫子,树木,消杀,x1,maxab
From: https://www.cnblogs.com/zongzw/p/18283702