2023-11-25：用go语言，给定一个数组arr，长度为n，表示n个格子

2023-11-25：用go语言，给定一个数组arr，长度为n，表示n个格子的分数，并且这些格子首尾相连，

孩子不能选相邻的格子，不能回头选，不能选超过一圈，

但是孩子可以决定从任何位置开始选，也可以什么都不选。

返回孩子能获得的最大分值。

1 <= n <= 10^6，

0 <= arr[i] <= 10^6。

来自华为od。

来自左程云。

答案2023-11-25：

go和c++的代码用灵捷3.5编写，感觉有点抽风了，生成的代码需要修改才能运行。

大体过程如下：

1.暴力方法（max1函数）

这种方法是一种递归的方式，通过尝试所有可能的组合来找到最大分值。

• •定义max1函数，接受一个长度为n的数组arr作为参数。
• •若arr的长度为1，直接返回arr[]作为结果。
• •否则，调用process函数，传入arr、起始索引和一个长度为n的布尔类型数组path（用于记录选择的路径）。
• •在process函数中，先检查是否已经遍历到数组末尾，若是，则判断首尾是否相连，如果是则返回最小整数值math.MinInt32，否则遍历整个数组检查相邻格子是否被选中，如果有返回最小整数值。
• •初始化ans为，遍历数组，如果path[j]为true，则将arr[j]加到ans上。
• •返回ans作为结果。

2.记忆化搜索（max2函数）

这种方法使用动态规划的思想，借助一个二维数组dp来存储已计算的结果，以减少重复计算。

• •定义max2函数，接受一个长度为n的数组arr作为参数。
• •若arr的长度为1，直接返回arr[]作为结果。
• •否则，初始化n为arr的长度，并创建一个二维数组dp，大小为[n][4]，并将其所有元素设置为最小整数值math.MinInt32。
• •初始化ans为arr[]加上调用process2函数的结果，传入arr、起始索引1、、和dp。
• •将ans更新为ans与调用process2函数，传入arr、起始索引1、、和dp的结果中的较大值。
• •返回ans作为结果。

3.正式方法（max3函数）

这种方法是一种严格位置依赖的动态规划方法，同时使用空间压缩技巧，减少额外空间的使用。

• •定义max3函数，接受一个长度为n的数组arr作为参数。
• •若arr的长度为1，直接返回arr[]作为结果。
• •否则，初始化n为arr的长度，并创建两个大小为4的一维数组next和cur，用于保存计算过程中的结果。
• •将next[]初始化为arr[n-1]的最大值和的较大值（即取和arr[n-1]的较大值）。
• •从n-2开始向前遍历数组arr，进行动态规划计算。
• •在每次遍历中，使用三重嵌套循环，遍历pre和end，计算cur[(pre<<1)|end]的值，其中<<为位运算符，|为按位或运算符。
• •更新next数组的值为cur数组的值。
• •最终，返回arr[]+next[3]和next[]中的较大值作为结果。

总结时间复杂度和空间复杂度：

• •第一种暴力方法的时间复杂度为O(2^n)，空间复杂度为O(n)。
• •第二种记忆化搜索的时间复杂度为O(n)，空间复杂度为O(n)。
• •第三种正式方法的时间复杂度为O(n)，空间复杂度为O(1)。

go完整代码如下：

packagemain
import(
"fmt"
"math"
"math/rand"
"time"
)
//暴力方法
funcmax1(arr[]int)int{
iflen(arr)==1{
returnarr[0]
}
returnprocess(arr,0,make([]bool,len(arr)))
}
funcprocess(arr[]int,iint,path[]bool)int{
ifi==len(arr){
ifpath[0]&&path[len(arr)-1]{
returnmath.MinInt32
}
forj:=1;jifpath[j-1]&&path[j]{
returnmath.MinInt32
}
}
ans:=0
forj:=0;jifpath[j]{
ans+=arr[j]
}
}
returnans
}else{
path[i]=true
ans1:=process(arr,i+1,path)
path[i]=false
ans2:=process(arr,i+1,path)
returnint(math.Max(float64(ans1),float64(ans2)))
}
}
//时间复杂度O(N)，记忆化搜索
funcmax2(arr[]int)int{
iflen(arr)==1{
returnarr[0]
}
n:=len(arr)
dp:=make([][]int,n)
fori:=0;idp[i]=make([]int,4)
forj:=0;j<4;j++{
dp[i][j]=math.MinInt32
}
}
ans:=arr[0]+process2(arr,1,1,1,dp)
ans=int(math.Max(float64(ans),float64(process2(arr,1,0,0,dp))))
returnans
}
funcprocess2(arr[]int,i,pre,endint,dp[][]int)int{
ifi==len(arr)-1{
returnValue:=0
ifpre==1||end==1{
returnreturnValue
}else{
returnint(math.Max(float64(returnValue),float64(arr[i])))
}
}else{
ifdp[i][(pre<<1)|end]!=math.MinInt32{
returndp[i][(pre<<1)|end]
}
p1:=process2(arr,i+1,0,end,dp)
p2:=math.MinInt32
ifpre!=1{
p2=arr[i]+process2(arr,i+1,1,end,dp)
}
ans:=int(math.Max(float64(p1),float64(p2)))
dp[i][(pre<<1)|end]=ans
returnans
}
}
//正式方法
//严格位置依赖的动态规划+空间压缩
//时间复杂度O(N)
funcmax3(arr[]int)int{
iflen(arr)==1{
returnarr[0]
}
n:=len(arr)
next:=make([]int,4)
cur:=make([]int,4)
next[0]=int(math.Max(0,float64(arr[n-1])))
fori:=n-2;i>=1;i--{
forpre:=0;pre<2;pre++{
forend:=0;end<2;end++{
cur[(pre<<1)|end]=next[end]
ifpre!=1{
cur[(pre<<1)|end]=int(math.Max(float64(cur[(pre<<1)|end]),float64(arr[i]+next[2+end])))
}
}
}
next[0]=cur[0]
next[1]=cur[1]
next[2]=cur[2]
next[3]=cur[3]
}
returnint(math.Max(float64(arr[0]+next[3]),float64(next[0])))
}
//为了测试
funcrandomArray(n,vint)[]int{
arr:=make([]int,n)
fori:=0;iarr[i]=int(math.Floor(float64(v)*rand.Float64()))
}
returnarr
}
funcmain(){
N:=16
V:=100
testTimes:=500
fmt.Println("测试开始")
rand.Seed(time.Now().UnixMilli())
fori:=0;in:=rand.Intn(N)+1
arr:=randomArray(n,V)
ans1:=max1(arr)
ans2:=max2(arr)
ans3:=max3(arr)
ifans1!=ans2||ans1!=ans3{
fmt.Println("出错了！",i)
return
}
}
fmt.Println("测试结束")
}

c++完整代码如下：

#include
#include
#include
#include
#include
usingnamespacestd;
intprocess(vector&arr,inti,vector&path);
intmax1(vector&arr){
if(arr.size()==1){
returnarr[0];
}
vectora=vector(arr.size(),false);
returnprocess(arr,0,a);
}
intprocess(vector&arr,inti,vector&path){
if(i==arr.size()){
if(path[0]&&path[arr.size()-1]){
returnINT32_MIN;
}
for(intj=1;jif(path[j-1]&&path[j]){
returnINT32_MIN;
}
}
intans=0;
for(intj=0;jif(path[j]){
ans+=arr[j];
}
}
returnans;
}
else{
path[i]=true;
intans1=process(arr,i+1,path);
path[i]=false;
intans2=process(arr,i+1,path);
returnmax(ans1,ans2);
}
}
intprocess2(vector&arr,inti,intpre,intend,vector

int>>&dp);
intmax2(vector&arr){
if(arr.size()==1){
returnarr[0];
}
intn=arr.size();
vector

int>>dp(n,vector(4,INT32_MIN));
intans=arr[0]+process2(arr,1,1,1,dp);
ans=max(ans,process2(arr,1,0,0,dp));
returnans;
}
intprocess2(vector&arr,inti,intpre,intend,vector

int>>&dp){
if(i==arr.size()-1){
intreturnValue=0;
if(pre==1||end==1){
returnreturnValue;
}
else{
returnmax(returnValue,arr[i]);
}
}
else{
if(dp[i][(pre<<1)|end]!=INT32_MIN){
returndp[i][(pre<<1)|end];
}
intp1=process2(arr,i+1,0,end,dp);
intp2=INT32_MIN;
if(pre!=1){
p2=arr[i]+process2(arr,i+1,1,end,dp);
}
intans=max(p1,p2);
dp[i][(pre<<1)|end]=ans;
returnans;
}
}
intmax3(vector&arr){
if(arr.size()==1){
returnarr[0];
}
intn=arr.size();
vectornext(4);
vectorcur(4);
next[0]=max(0,arr[n-1]);
for(inti=n-2;i>=1;i--){
for(intpre=0;pre<2;pre++){
for(intend=0;end<2;end++){
cur[(pre<<1)|end]=next[end];
if(pre!=1){
cur[(pre<<1)|end]=max(cur[(pre<<1)|end],arr[i]+next[2+end]);
}
}
}
next[0]=cur[0];
next[1]=cur[1];
next[2]=cur[2];
next[3]=cur[3];
}
returnmax(arr[0]+next[3],next[0]);
}
vectorrandomArray(intn,intv){
vectorarr(n);
srand(time(NULL));
for(inti=0;iarr[i]=floor(v*((double)rand()/RAND_MAX));
}
returnarr;
}
intmain(){
intN=16;
intV=100;
inttestTimes=500;
cout<<"测试开始"<for(inti=0;iintn=rand()%N+1;
vectorarr=randomArray(n,V);
intans1=max1(arr);
intans2=max2(arr);
intans3=max3(arr);
if(ans1!=ans2||ans1!=ans3){
cout<<"出错了！"<return0;
}
}
cout<<"测试结束"<return0;
}