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

2023-12-20 03:15
文章标签 语言 go 数组 16 2023 元素 删除 最大值 字节 累加 整数 长度 来自 给定 arr 任一

本文主要是介绍2023-12-16：用go语言，给定整数数组arr，求删除任一元素后， 新数组中长度为k的子数组累加和的最大值。 来自字节。，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

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

来自字节。

答案2023-12-16：

来自左程云。

灵捷3.5

大体步骤如下：

算法 maxSum1 分析：

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

2.如果 n <= k，则返回 0。

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 <= k，则返回 0。

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 mainimport ("fmt""math""math/rand""time"
)func maxSum1(arr []int, k int) int {n := len(arr)if n <= k {return 0}ans := math.MinInt32for i := 0; i < n; 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) - 1ans := make([]int, len0)i := 0for j := 0; j < len(arr); j++ {if j != index {ans[i] = arr[j]i++}}return ans
}func lenKmaxSum(arr []int, k int) int {n := len(arr)ans := math.MinInt32for i := 0; i <= n-k; i++ {cur := 0for j, cnt := i, 0; cnt < k; j, cnt = j+1, cnt+1 {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 <= k {return 0}window := make([]int, n)l, r := 0, 0var sum int64 = 0ans := math.MinInt32for i := 0; i < n; i++ {for l < r && arr[window[r-1]] >= arr[i] {r--}window[r] = ir++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 < n; i++ {arr[i] = rand.Intn(2*v+1) - v}return arr
}func main() {N := 100V := 1000testTimes := 10000fmt.Println("测试开始")rand.Seed(time.Now().Unix())for i := 0; i < testTimes; i++ {rand.Intn(N)n := rand.Intn(N) + 1arr := randomArray(n, V)k := rand.Intn(N) + 1ans1 := maxSum1(arr, k)ans2 := maxSum2(arr, k)if ans1 != ans2 {fmt.Println("出错了!")}}fmt.Println("测试结束")
}

在这里插入图片描述

c++完整代码如下：

#include <iostream>
#include <vector>
#include <cmath>
#include <cstdlib>
#include <ctime>using namespace std;int lenKmaxSum(const vector<int>& arr, int k);int maxSum1(vector<int>& arr, int k) {int n = arr.size();if (n <= k) {return 0;}int ans = INT_MIN;for (int i = 0; i < n; i++) {vector<int> rest(arr.begin(), arr.end());rest.erase(rest.begin() + i);ans = max(ans, lenKmaxSum(rest, k));}return ans;
}int lenKmaxSum(const vector<int>& arr, int k) {int n = arr.size();int ans = INT_MIN;for (int i = 0; i <= n - k; i++) {int cur = 0;for (int j = i, cnt = 0; cnt < k; j++, cnt++) {cur += arr[j];}ans = max(ans, cur);}return ans;
}int maxSum2(const vector<int>& arr, int k) {int n = arr.size();if (n <= k) {return 0;}vector<int> window(n);int l = 0, r = 0;long long sum = 0;int ans = INT_MIN;for (int i = 0; i < n; i++) {while (l < r && arr[window[r - 1]] >= arr[i]) {r--;}window[r] = i;r++;sum += arr[i];if (i >= k) {ans = max(ans, static_cast<int>(sum - arr[window[l]]));if (window[l] == i - k) {l++;}sum -= arr[i - k];}}return ans;
}void randomArray(vector<int>& arr, int n, int v) {arr.resize(n);for (int i = 0; i < n; i++) {arr[i] = rand() % (2 * v + 1) - v;}
}int main() {const int N = 100;const int V = 1000;const int TEST_TIMES = 10000;cout << "测试开始" << endl;srand(time(NULL));for (int i = 0; i < TEST_TIMES; i++) {int n = rand() % N + 1;vector<int> arr;randomArray(arr, n, V);int k = rand() % N + 1;int ans1 = maxSum1(arr, k);int ans2 = maxSum2(arr, k);if (ans1 != ans2) {cout << "出错了!" << endl;}}cout << "测试结束" << endl;return 0;
}

在这里插入图片描述

c完整代码如下：

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>#define int64_t long longint64_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 <= k) {return 0;}int64_t ans = LLONG_MIN;for (int64_t i = 0; i < size; i++) {int64_t* rest = malloc((size - 1) * sizeof(int64_t));int64_t restIndex = 0;for (int64_t j = 0; j < size; 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 <= size - k; i++) {int64_t cur = 0;for (int64_t j = i, cnt = 0; cnt < k; j++, cnt++) {cur += arr[j];}ans = max(ans, cur);}return ans;
}int64_t maxSum2(int64_t* arr, int64_t size, int64_t k) {if (size <= k) {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 < size; i++) {while (l < r && arr[window[r - 1]] >= 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 < size; 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 < TEST_TIMES; 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;
}

在这里插入图片描述

这篇关于2023-12-16：用go语言，给定整数数组arr，求删除任一元素后， 新数组中长度为k的子数组累加和的最大值。 来自字节。的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/514608。

相关文章

C语言中位操作的实际应用举例

C语言中位操作的实际应用举例

《C语言中位操作的实际应用举例》：本文主要介绍C语言中位操作的实际应用,总结了位操作的使用场景,并指出了需要注意的问题,如可读性、平台依赖性和溢出风险,文中通过代码介绍的非常详细,需要的朋友可以参... 目录1. 嵌入式系统与硬件寄存器操作2. 网络协议解析3. 图像处理与颜色编码4. 高效处理布尔标志集合
阅读更多...
Go语言开发实现查询IP信息的MCP服务器

Go语言开发实现查询IP信息的MCP服务器

《Go语言开发实现查询IP信息的MCP服务器》随着MCP的快速普及和广泛应用,MCP服务器也层出不穷,本文将详细介绍如何在Go语言中使用go-mcp库来开发一个查询IP信息的MCP... 目录前言mcp-ip-geo 服务器目录结构说明查询 IP 信息功能实现工具实现工具管理查询单个 IP 信息工具的实现服
阅读更多...
C 语言中enum枚举的定义和使用小结

C 语言中enum枚举的定义和使用小结

《C语言中enum枚举的定义和使用小结》在C语言里,enum（枚举）是一种用户自定义的数据类型,它能够让你创建一组具名的整数常量,下面我会从定义、使用、特性等方面详细介绍enum,感兴趣的朋友一起看... 目录1、引言2、基本定义3、定义枚举变量4、自定义枚举常量的值5、枚举与switch语句结合使用6、枚
阅读更多...
redis过期key的删除策略介绍

redis过期key的删除策略介绍

《redis过期key的删除策略介绍》：本文主要介绍redis过期key的删除策略,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录第一种策略：被动删除第二种策略：定期删除第三种策略：强制删除关于big key的清理UNLINK命令FLUSHALL/FLUSHDB命
阅读更多...
Java数组初始化的五种方式

Java数组初始化的五种方式

《Java数组初始化的五种方式》数组是Java中最基础且常用的数据结构之一,其初始化方式多样且各具特点,本文详细讲解Java数组初始化的五种方式,分析其适用场景、优劣势对比及注意事项,帮助避免常见陷阱... 目录1. 静态初始化：简洁但固定代码示例核心特点适用场景注意事项2. 动态初始化：灵活但需手动管理代
阅读更多...
go 指针接收者和值接收者的区别小结

go 指针接收者和值接收者的区别小结

《go指针接收者和值接收者的区别小结》在Go语言中,值接收者和指针接收者是方法定义中的两种接收者类型,本文主要介绍了go指针接收者和值接收者的区别小结,文中通过示例代码介绍的非常详细,需要的朋友们下... 目录go 指针接收者和值接收者的区别易错点辨析go 指针接收者和值接收者的区别指针接收者和值接收者的
阅读更多...
C++中初始化二维数组的几种常见方法

C++中初始化二维数组的几种常见方法

《C++中初始化二维数组的几种常见方法》本文详细介绍了在C++中初始化二维数组的不同方式,包括静态初始化、循环、全部为零、部分初始化、std::array和std::vector,以及std::vec... 目录1. 静态初始化2. 使用循环初始化3. 全部初始化为零4. 部分初始化5. 使用 std::a
阅读更多...
shell编程之函数与数组的使用详解

shell编程之函数与数组的使用详解

《shell编程之函数与数组的使用详解》：本文主要介绍shell编程之函数与数组的使用,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录shell函数函数的用法俩个数求和系统资源监控并报警函数函数变量的作用范围函数的参数递归函数shell数组获取数组的长度读取某下的
阅读更多...
Go 语言中的select语句详解及工作原理

Go 语言中的select语句详解及工作原理

《Go语言中的select语句详解及工作原理》在Go语言中,select语句是用于处理多个通道（channel）操作的一种控制结构,它类似于switch语句,本文给大家介绍Go语言中的select语... 目录Go 语言中的 select 是做什么的基本功能语法工作原理示例示例 1：监听多个通道示例 2：带
阅读更多...
如何高效移除C++关联容器中的元素

如何高效移除C++关联容器中的元素

《如何高效移除C++关联容器中的元素》关联容器和顺序容器有着很大不同,关联容器中的元素是按照关键字来保存和访问的,而顺序容器中的元素是按它们在容器中的位置来顺序保存和访问的,本文介绍了如何高效移除C+... 目录一、简介二、移除给定位置的元素三、移除与特定键值等价的元素四、移除满足特android定条件的元
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2