返回一个数组中,选择的数字不能相邻的情况下, 最大子序列累加和。
方法一:自然智慧。递归。
方法二:动态规划。
思路:
定义dp[i] : 表示arr[0…i]范围上,在不能取相邻数的情况下,返回所有组合中的最大累加和
在arr[0…i]范围上,在不能取相邻数的情况下,得到的最大累加和,可能性分类:
可能性 1) 选出的组合,不包含arr[i]。那么dp[i] = dp[i-1]
比如,arr[0…i] = {3,4,-4},最大累加和是不包含i位置数的时候
可能性 2) 选出的组合,只包含arr[i]。那么dp[i] = arr[i]
比如,arr[0…i] = {-3,-4,4},最大累加和是只包含i位置数的时候
可能性 3) 选出的组合,包含arr[i], 且包含arr[0…i-2]范围上的累加和。那么dp[i] = arr[i] + dp[i-2]
比如,arr[0…i] = {3,1,4},最大累加和是3和4组成的7,因为相邻不能选,所以i-1位置的数要跳过
综上所述:dp[i] = Max { dp[i-1], arr[i] , arr[i] + dp[i-2] }
代码用golang编写。代码如下:
package main
import (
"fmt"
"math/rand"
"time"
)
func main() {
rand.Seed(time.Now().Unix())
const TOTAL = 100000
count := 0
for i := 0; i < TOTAL; i++ {
arr := genRandArr()
ret1 := maxSum1(arr)
ret2 := maxSum2(arr)
fmt.Println(ret1, ret2, arr)
if ret1 == ret2 {
count++
}
}
fmt.Println("总数:", TOTAL)
fmt.Println("正确数:", count)
}
//递归
func maxSum1(arr []int) int {
N := len(arr)
if N == 0 {
return 0
}
if N == 1 {
return arr[0]
}
ans := -1
for i := 0; i < N; i++ {
if arr[i] > 0 {
ans = process1(arr, i)
if i+1 < N && arr[i] > 0 {
ans = getMax(ans, process1(arr, i+1))
}
break
}
}
if ans < 0 {
ans = arr[0]
for i := 1; i < N; i++ {
ans = getMax(ans, arr[i])
}
}
return ans
}
func process1(arr []int, start int) int {
N := len(arr)
if start >= N {
return 0
}
ans := 0
for i := start + 2; i < N; i++ {
if arr[i] > 0 {
ans = getMax(ans, process1(arr, i))
}
}
ans += arr[start]
//fmt.Println(start, "arr[start] = ", arr[start])
return ans
}
func getMax(a int, b int) int {
if a > b {
return a
} else {
return b
}
}
// 给定一个数组arr,在不能取相邻数的情况下,返回所有组合中的最大累加和
// 思路:
// 定义dp[i] : 表示arr[0...i]范围上,在不能取相邻数的情况下,返回所有组合中的最大累加和
// 在arr[0...i]范围上,在不能取相邻数的情况下,得到的最大累加和,可能性分类:
// 可能性 1) 选出的组合,不包含arr[i]。那么dp[i] = dp[i-1]
// 比如,arr[0...i] = {3,4,-4},最大累加和是不包含i位置数的时候
//
// 可能性 2) 选出的组合,只包含arr[i]。那么dp[i] = arr[i]
// 比如,arr[0...i] = {-3,-4,4},最大累加和是只包含i位置数的时候
//
// 可能性 3) 选出的组合,包含arr[i], 且包含arr[0...i-2]范围上的累加和。那么dp[i] = arr[i] + dp[i-2]
// 比如,arr[0...i] = {3,1,4},最大累加和是3和4组成的7,因为相邻不能选,所以i-1位置的数要跳过
//
// 综上所述:dp[i] = Max { dp[i-1], arr[i] , arr[i] + dp[i-2] }
func maxSum2(arr []int) int {
if len(arr) == 0 {
return 0
}
N := len(arr)
if N == 1 {
return arr[0]
}
if N == 2 {
return getMax(arr[0], arr[1])
}
dp := make([]int, N)
dp[0] = arr[0]
dp[1] = getMax(arr[0], arr[1])
for i := 2; i < N; i++ {
dp[i] = getMax(getMax(dp[i-1], arr[i]), arr[i]+dp[i-2])
}
return dp[N-1]
}
func genRandArr() []int {
ans := make([]int, rand.Intn(10)+5)
for i := 0; i < len(ans); i++ {
ans[i] = rand.Intn(100) - 90
}
return ans
}
执行结果如下: