2023-12-16：用go语言，给定整数数组arr，求删除任一元素后， 新数组中长度为k的子数组累加和的最大值。 来自字节。

2023-12-16：用go语言，给定整数数组arr，求删除任一元素后，

新数组中长度为k的子数组累加和的最大值。

来自字节。

答案2023-12-16：

来自左程云。

灵捷3.5

大体步骤如下：

算法 maxSum1 分析：

1.计算输入数组 arr 的长度 n。

2.如果 n

3.初始化 ans 为 int 类型的最小值(math.MinInt32)。

4.对于每个数组元素 arr[i]，执行以下步骤：

4.a.删除第 i 个元素，得到新的数组 rest。

4.b.计算新数组 rest 的长度为 k 的子数组累加和的最大值，使用函数 lenKmaxSum(rest, k)。

4.c.将 ans 更新为 ans 和 lenKmaxSum(rest, k) 中的较大值。

5.返回 ans。

算法 delete 分析：

1.计算输入数组 arr 的长度 len0，即 len(arr) - 1。

2.创建一个长度为 len0 的新数组 ans。

3.初始化索引 i 为 0。

4.对于数组 arr 的每个元素 arr[j]，执行以下步骤：

4.a.如果 j 不等于给定的索引 index，则将 arr[j] 赋值给 ans[i]。

4.b.将 i 递增 1。

5.返回新数组 ans。

算法 lenKmaxSum 分析：

1.计算输入数组 arr 的长度 n。 2.初始化 ans 为 int 类型的最小值(math.MinInt32)。 3.对于每个起始位置 i，从 i 到 i + (n - k) 执行以下步骤： 3.a.初始化 cur 为 0。 3.b.对于每个元素 arr[j]，从 i 开始计数，执行以下步骤，直到计数 cnt 达到 k： 3.b. i.将 arr[j] 加到 cur 中。 3.b. ii.增加计数 cnt。 3.c.将 ans 更新为 ans 和 cur 中的较大值。 4.返回 ans。

算法 maxSum2 分析：

1.计算输入数组 arr 的长度 n。

2.如果 n

3.创建一个长度为 n 的窗口(window)数组。

4.初始化左指针 l 和右指针 r 为 0。

5.初始化变量 sum 为 0，并使用 int64 类型存储。

6.初始化 ans 为 int 类型的最小值(math.MinInt32)。

7.对于每个索引 i，从 0 到 n-1 执行以下步骤：

7.a.当窗口不为空且窗口中最后一个元素 arr[window[r-1]] 大于等于当前元素 arr[i] 时，移动右指针 r 减小窗口大小直至条件不满足。

7.b.将当前索引 i 添加到窗口中，即 window[r] = i，并递增右指针 r。

7.c.将当前元素 arr[i] 加到 sum 中。

7.d.如果 i >= k，说明窗口大小已达到 k，执行以下步骤：

7.d. i.将 ans 更新为 ans 和 sum 减去窗口左边界元素 arr[window[l]] 的较大值。

7.d. ii.如果窗口的左边界元素 arr[window[l]] 等于 i-k，说明该元素已经不在窗口内，移动左指针 l。

7.d. iii.从 sum 中减去窗口左边界元素 arr[i-k]。

8.返回 ans。

总的时间复杂度：

• maxSum1 算法的时间复杂度为 O(n^2)。

• delete 算法的时间复杂度为 O(n)。

• lenKmaxSum 算法的时间复杂度为 O(n*k)。

• maxSum2 算法的时间复杂度为 O(n)。

总的额外空间复杂度：

• maxSum1 算法的额外空间复杂度为 O(n)。

• delete 算法的额外空间复杂度为 O(n)。

• lenKmaxSum 算法的额外空间复杂度为 O(1)。

• maxSum2 算法的额外空间复杂度为 O(n)。

go完整代码如下：

package main

import (

"fmt"

"math"

"math/rand"

"time"

)

func maxSum1(arr []int, k int) int {

n := len(arr)

if n 

return 0

}

ans := math.MinInt32

for i := 0; i 

rest := delete(arr, i)

ans = int(math.Max(float64(ans), float64(lenKmaxSum(rest, k))))

}

return ans

}

func delete(arr []int, index int) []int {

len0 := len(arr) - 1

ans := make([]int, len0)

i := 0

for j := 0; j 

if j != index {

ans[i] = arr[j]

i++

}

}

return ans

}

func lenKmaxSum(arr []int, k int) int {

n := len(arr)

ans := math.MinInt32

for i := 0; i 

cur := 0

for j, cnt := i, 0; cnt 

cur += arr[j]

}

ans = int(math.Max(float64(ans), float64(cur)))

}

return ans

}

func maxSum2(arr []int, k int) int {

n := len(arr)

if n 

return 0

}

window := make([]int, n)

l, r := 0, 0

var sum int64 = 0

ans := math.MinInt32

for i := 0; i 

for l = arr[i] {

r--

}

window[r] = i

r++

sum += int64(arr[i])

if i >= k {

ans = int(math.Max(float64(ans), float64(sum-int64(arr[window[l]]))))

if window[l] == i-k {

l++

}

sum -= int64(arr[i-k])

}

}

return ans

}

func randomArray(n, v int) []int {

arr := make([]int, n)

for i := 0; i 

arr[i] = rand.Intn(2*v+1) - v

}

return arr

}

func main() {

N := 100

V := 1000

testTimes := 10000

fmt.Println("测试开始")

rand.Seed(time.Now().Unix())

for i := 0; i 

rand.Intn(N)

n := rand.Intn(N) + 1

arr := randomArray(n, V)

k := rand.Intn(N) + 1

ans1 := maxSum1(arr, k)

ans2 := maxSum2(arr, k)

if ans1 != ans2 {

fmt.Println("出错了!")

}

}

fmt.Println("测试结束")

}

在这里插入图片描述c++完整代码如下：

#include 

#include 

#include 

#include 

#include 

using namespace std;

int lenKmaxSum(const vector& arr, int k);

int maxSum1(vector& arr, int k) {

int n = arr.size();

if (n 

return 0;

}

int ans = INT_MIN;

for (int i = 0; i 

vector rest(arr.begin(), arr.end());

rest.erase(rest.begin() + i);

ans = max(ans, lenKmaxSum(rest, k));

}

return ans;

}

int lenKmaxSum(const vector& arr, int k) {

int n = arr.size();

int ans = INT_MIN;

for (int i = 0; i 

int cur = 0;

for (int j = i, cnt = 0; cnt 

cur += arr[j];

}

ans = max(ans, cur);

}

return ans;

}

int maxSum2(const vector& arr, int k) {

int n = arr.size();

if (n 

return 0;

}

vector window(n);

int l = 0, r = 0;

long long sum = 0;

int ans = INT_MIN;

for (int i = 0; i 

while (l = arr[i]) {

r--;

}

window[r] = i;

r++;

sum += arr[i];

if (i >= k) {

ans = max(ans, static_cast(sum - arr[window[l]]));

if (window[l] == i - k) {

l++;

}

sum -= arr[i - k];

}

}

return ans;

}

void randomArray(vector& arr, int n, int v) {

arr.resize(n);

for (int i = 0; i 

arr[i] = rand() % (2 * v + 1) - v;

}

}

int main() {

const int N = 100;

const int V = 1000;

const int TEST_TIMES = 10000;

cout 

srand(time(NULL));

for (int i = 0; i 

int n = rand() % N + 1;

vector arr;

randomArray(arr, n, V);

int k = rand() % N + 1;

int ans1 = maxSum1(arr, k);

int ans2 = maxSum2(arr, k);

if (ans1 != ans2) {

cout 

}

}

cout 

return 0;

}

在这里插入图片描述c完整代码如下：

#include 

#include 

#include 

#include 

#define int64_t long long

int64_t max0(int64_t a, int64_t b) {

return (a > b) ? a : b;

}

int64_t lenKmaxSum(int64_t* arr, int64_t size, int64_t k);

int64_t maxSum1(int64_t* arr, int64_t size, int64_t k) {

if (size 

return 0;

}

int64_t ans = LLONG_MIN;

for (int64_t i = 0; i 

int64_t* rest = malloc((size - 1) * sizeof(int64_t));

int64_t restIndex = 0;

for (int64_t j = 0; j 

if (j != i) {

rest[restIndex] = arr[j];

restIndex++;

}

}

ans = max0(ans, lenKmaxSum(rest, size - 1, k));

free(rest);

}

return ans;

}

int64_t lenKmaxSum(int64_t* arr, int64_t size, int64_t k) {

int64_t ans = LLONG_MIN;

for (int64_t i = 0; i 

int64_t cur = 0;

for (int64_t j = i, cnt = 0; cnt 

cur += arr[j];

}

ans = max(ans, cur);

}

return ans;

}

int64_t maxSum2(int64_t* arr, int64_t size, int64_t k) {

if (size 

return 0;

}

int64_t* window = malloc(size * sizeof(int64_t));

int64_t l = 0, r = 0;

int64_t sum = 0;

int64_t ans = LLONG_MIN;

for (int64_t i = 0; i 

while (l = arr[i]) {

r--;

}

window[r] = i;

r++;

sum += arr[i];

if (i >= k) {

ans = max0(ans, sum - arr[window[l]]);

if (window[l] == i - k) {

l++;

}

sum -= arr[i - k];

}

}

free(window);

return ans;

}

void randomArray(int64_t* arr, int64_t size, int64_t v) {

for (int64_t i = 0; i 

arr[i] = rand() % (2 * v + 1) - v;

}

}

int main() {

const int64_t N = 100;

const int64_t V = 1000;

const int64_t TEST_TIMES = 10000;

printf("测试开始\n");

srand(time(NULL));

for (int64_t i = 0; i 

int64_t n = rand() % N + 1;

int64_t* arr = malloc(n * sizeof(int64_t));

randomArray(arr, n, V);

int64_t k = rand() % N + 1;

int64_t ans1 = maxSum1(arr, n, k);

int64_t ans2 = maxSum2(arr, n, k);

if (ans1 != ans2) {

printf("出错了!\n");

}

free(arr);

}

printf("测试结束\n");

return 0;

}

在这里插入图片描述