2023-11-25：用 go 语言，给定一个数组 arr，长度为 n，表示 n 个格子的分数，并且这些格子首尾相连，孩子不能选相邻的格子，不能回头选，不能选超过一圈，但是孩子可以决定从任何位置开始选，也可以

作者：福大大架构师每日一题

2023-11-25
北京
本文字数：4330 字
阅读完需：约 14 分钟

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 完整代码如下：

package main
import (  "fmt"  "math"  "math/rand"  "time")
// 暴力方法func max1(arr []int) int {  if len(arr) == 1 {    return arr[0]  }  return process(arr, 0, make([]bool, len(arr)))}
func process(arr []int, i int, path []bool) int {  if i == len(arr) {    if path[0] && path[len(arr)-1] {      return math.MinInt32    }    for j := 1; j < len(arr); j++ {      if path[j-1] && path[j] {        return math.MinInt32      }    }    ans := 0    for j := 0; j < len(arr); j++ {      if path[j] {        ans += arr[j]      }    }    return ans  } else {    path[i] = true    ans1 := process(arr, i+1, path)    path[i] = false    ans2 := process(arr, i+1, path)    return int(math.Max(float64(ans1), float64(ans2)))  }}
// 时间复杂度O(N)，记忆化搜索func max2(arr []int) int {  if len(arr) == 1 {    return arr[0]  }  n := len(arr)  dp := make([][]int, n)  for i := 0; i < n; i++ {    dp[i] = make([]int, 4)    for j := 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))))  return ans}
func process2(arr []int, i, pre, end int, dp [][]int) int {  if i == len(arr)-1 {    returnValue := 0    if pre == 1 || end == 1 {      return returnValue    } else {      return int(math.Max(float64(returnValue), float64(arr[i])))    }  } else {    if dp[i][(pre<<1)|end] != math.MinInt32 {      return dp[i][(pre<<1)|end]    }    p1 := process2(arr, i+1, 0, end, dp)    p2 := math.MinInt32    if pre != 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    return ans  }}
// 正式方法// 严格位置依赖的动态规划 + 空间压缩// 时间复杂度O(N)func max3(arr []int) int {  if len(arr) == 1 {    return arr[0]  }  n := len(arr)  next := make([]int, 4)  cur := make([]int, 4)  next[0] = int(math.Max(0, float64(arr[n-1])))  for i := n - 2; i >= 1; i-- {    for pre := 0; pre < 2; pre++ {      for end := 0; end < 2; end++ {        cur[(pre<<1)|end] = next[end]        if pre != 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]  }  return int(math.Max(float64(arr[0]+next[3]), float64(next[0])))}
// 为了测试func randomArray(n, v int) []int {  arr := make([]int, n)  for i := 0; i < n; i++ {    arr[i] = int(math.Floor(float64(v) * rand.Float64()))  }  return arr}
func main() {  N := 16  V := 100  testTimes := 500  fmt.Println("测试开始")  rand.Seed(time.Now().UnixMilli())  for i := 0; i < testTimes; i++ {    n := rand.Intn(N) + 1    arr := randomArray(n, V)    ans1 := max1(arr)    ans2 := max2(arr)    ans3 := max3(arr)    if ans1 != ans2 || ans1 != ans3 {      fmt.Println("出错了！", i)      return    }  }  fmt.Println("测试结束")}

复制代码

c++完整代码如下：

#include <iostream>#include <vector>#include <algorithm>#include <cmath>#include <ctime>
using namespace std;
int process(vector<int>& arr, int i, vector<bool>& path);
int max1(vector<int>& arr) {    if (arr.size() == 1) {        return arr[0];    }    vector<bool> a = vector<bool>(arr.size(), false);    return process(arr,0 , a);}
int process(vector<int>& arr, int i, vector<bool>& path) {    if (i == arr.size()) {        if (path[0] && path[arr.size() - 1]) {            return INT32_MIN;        }        for (int j = 1; j < arr.size(); j++) {            if (path[j - 1] && path[j]) {                return INT32_MIN;            }        }        int ans = 0;        for (int j = 0; j < arr.size(); j++) {            if (path[j]) {                ans += arr[j];            }        }        return ans;    }    else {        path[i] = true;        int ans1 = process(arr, i + 1, path);        path[i] = false;        int ans2 = process(arr, i + 1, path);        return max(ans1, ans2);    }}
int process2(vector<int>& arr, int i, int pre, int end, vector<vector<int>>& dp);
int max2(vector<int>& arr) {    if (arr.size() == 1) {        return arr[0];    }    int n = arr.size();    vector<vector<int>> dp(n, vector<int>(4, INT32_MIN));    int ans = arr[0] + process2(arr, 1, 1, 1, dp);    ans = max(ans, process2(arr, 1,0 ,0 , dp));    return ans;}
int process2(vector<int>& arr, int i, int pre, int end, vector<vector<int>>& dp) {    if (i == arr.size() - 1) {        int returnValue =0 ;        if (pre == 1 || end == 1) {            return returnValue;        }        else {            return max(returnValue, arr[i]);        }    }    else {        if (dp[i][(pre << 1) | end] != INT32_MIN) {            return dp[i][(pre << 1) | end];        }        int p1 = process2(arr, i + 1,0 , end, dp);        int p2 = INT32_MIN;        if (pre != 1) {            p2 = arr[i] + process2(arr, i + 1, 1, end, dp);        }        int ans = max(p1, p2);        dp[i][(pre << 1) | end] = ans;        return ans;    }}
int max3(vector<int>& arr) {    if (arr.size() == 1) {        return arr[0];    }    int n = arr.size();    vector<int> next(4);    vector<int> cur(4);    next[0] = max(0, arr[n - 1]);    for (int i = n - 2; i >= 1; i--) {        for (int pre = 0; pre < 2; pre++) {            for (int end = 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];    }    return max(arr[0] + next[3], next[0]);}
vector<int> randomArray(int n, int v) {    vector<int> arr(n);    srand(time(NULL));    for (int i = 0; i < n; i++) {        arr[i] = floor(v * ((double)rand() / RAND_MAX));    }    return arr;}
int main() {    int N = 16;    int V = 100;    int testTimes = 500;    cout << "测试开始" << endl;    for (int i = 0; i < testTimes; i++) {        int n = rand() % N + 1;        vector<int> arr = randomArray(n, V);        int ans1 = max1(arr);        int ans2 = max2(arr);        int ans3 = max3(arr);        if (ans1 != ans2 || ans1 != ans3) {            cout << "出错了！" << i << endl;            return 0;        }    }    cout << "测试结束" << endl;    return 0;}