2021-06-16：返回一个数组中，选择的数字不能相邻的情况下， 最大子序列累加和。
福大大 答案2021-06-16：
方法一：自然智慧。递归。
方法二：动态规划。
思路：
定义dpi : 表示arr0...i范围上，在不能取相邻数的情况下，返回所有组合中的最大累加和
在arr0...i范围上，在不能取相邻数的情况下，得到的最大累加和，可能性分类：
可能性 1) 选出的组合，不包含arri。那么dpi = dpi-1
比如，arr0...i = {3,4,-4}，最大累加和是不包含i位置数的时候
可能性 2) 选出的组合，只包含arri。那么dpi = arri
比如，arr0...i = {-3,-4,4}，最大累加和是只包含i位置数的时候
可能性 3) 选出的组合，包含arri, 且包含arr0...i-2范围上的累加和。那么dpi = arri dpi-2
比如，arr0...i = {3,1,4}，最大累加和是3和4组成的7，因为相邻不能选，所以i-1位置的数要跳过
综上所述：dpi = Max { dpi-1, arri , arri dpi-2 }
代码用golang编写。代码如下：
代码语言：txt复制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
}执行结果如下：
图片左神java代码
