0基础做下载网站,注册安全工程师是干什么的,内容管理系统开发,wordpress 前台发布文章2023-12-16#xff1a;用go语言#xff0c;给定整数数组arr#xff0c;求删除任一元素后#xff0c;
新数组中长度为k的子数组累加和的最大值。
来自字节。
答案2023-12-16#xff1a;
来自左程云。
灵捷3.5
大体步骤如下#xff1a;
算法 maxSum1 分析#xff1…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 (fmtmathmath/randtime
)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 j1, cnt1 {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] irsum 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*v1) - 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 ctimeusing namespace std;int lenKmaxSum(const vectorint arr, int k);int maxSum1(vectorint arr, int k) {int n arr.size();if (n k) {return 0;}int ans INT_MIN;for (int i 0; i n; i) {vectorint rest(arr.begin(), arr.end());rest.erase(rest.begin() i);ans max(ans, lenKmaxSum(rest, k));}return ans;
}int lenKmaxSum(const vectorint 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 vectorint arr, int k) {int n arr.size();if (n k) {return 0;}vectorint 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_castint(sum - arr[window[l]]));if (window[l] i - k) {l;}sum - arr[i - k];}}return ans;
}void randomArray(vectorint 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;vectorint 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;
}
