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

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

时间：2023-12-16 21:33:08浏览次数：37  
标签：arr 12 int window int64 数组 ans

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 main

import (
	"fmt"
	"math"
	"math/rand"
	"time"
)

func maxSum1(arr []int, k int) int {
	n := len(arr)
	if n <= k {
		return 0
	}
	ans := math.MinInt32
	for 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) - 1
	ans := make([]int, len0)
	i := 0
	for 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.MinInt32
	for i := 0; i <= n-k; i++ {
		cur := 0
		for 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, 0
	var sum int64 = 0
	ans := math.MinInt32
	for i := 0; i < n; i++ {
		for l < r && arr[window[r-1]] >= 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 < n; 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 < testTimes; 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 <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 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 <= 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;
}

在这里插入图片描述

标签：arr,12,int,window,int64,数组,ans
From： https://www.cnblogs.com/moonfdd/p/17908412.html

相关文章

  • 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)......
  • 数组篇2
    数组简介集合、列表和数组集合集合里的元素类型不一定相同（可以同时有String和int）集合里的元素没有顺序（因此，不会有在集合里找第一个元素的说法）列表列表（又称线性列表）的定义为：是一种数据项构成的有限序列，即按照一定的线性顺序，排列而成的数据项的集合。列表的概念是在集合的......
  • 【2023潇湘夜雨】WIN10_Pro_22H2.19045.3803软件选装纯净版12.15
    【系统简介】=============================================================1.本次更新母盘来自WIN10_Pro_22H2.19045.3803。2.增加部分优化方案，手工精简部分较多。3.OS版本号为19045.3803。精简系统只是为部分用户安装，个别要求高的去MSDN下。4.集成《DrvCeo-2.15.0.5》网卡版、......
  • 2023-2024-120232325《网络空间安全导论》第六周学习
    教材内容总结问题1.零信任模型的优缺点:优点：提供了更高的安全性：零信任模型将网络安全的重点放在身份验证和授权上，可以更好地防止未经授权的访问和数据泄露。降低了内部威胁：零信任模型不信任任何用户或设备，因此即使是内部人员也需要经过严格的身份验证才能访问敏感信息，可以减......
  • 12.16每日总结
    首先还是展示架构image用来存储图片，api请求token，changecode用来存放图片转base64的代码（base64->changecode），ui放界面，mian用于启动！！，其余是百度图像的专用工具，你们申请然后使用人家的接口时就能看到image文件夹存储图片，里边的不叫image的是基础图片，他们经过转换都叫image。 然后......
  • 12.16记
    还是没能走上捷径。但或许本来就应该这样，我的命运就是如此，若是获得些梦幻般的事物，就理所应当失去，即便挣扎又如何，依然是失去。我如此不堪，堕落，浑浊，却无知地希冀着本不属于我的事物，被打了一巴掌之后才能清醒过来，然后继续去争取。道就应该这样吗？或许吧。或许有些东西还未失去，甚至......
  • 如何写出漂亮代码 https://libin9ioak.blog.csdn.net/article/details/127749042
    从代码的编写规范，格式的优化，设计原则和一些常见的代码优化的技巧等方面总结了45个小技巧： 1、规范命名命名是写代码中最频繁的操作，比如类、属性、方法、参数等。好的名字应当能遵循以下几点：见名知意比如需要定义一个变量需要来计数inti=0;1名称i没有任何的实际意义，没有......
  • 闲话 2023.12.16
    从今天晚上开始要血战一整天了......
  • 12.16
    超级钢琴写了三个小时。然后光顾着调题啥也没干。唐了，交了几遍都只拿了十分，把每个部分检查完后发现原来是DP数组开小了......
  • 20231329 《计算机基础与程序设计》第12周学习总结
    作业信息这个作业属于哪个课程https://edu.cnblogs.com/campus/besti/2023-2024-1-CFAP这个作业要求在哪里https://www.cnblogs.com/rocedu/p/9577842.html#WEEK12这个作业的目标《C语言程序设计》第11章并完成云班课测试作业正文https://www.cnblogs.com/xjn1......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99