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

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

packagemain
import(
"fmt"
"math"
"math/rand"
"time"
)
funcmaxSum1(arr[]int,kint)int{
n:=len(arr)
ifn<=k{
return0
}
ans:=math.MinInt32
fori:=0;irest:=delete(arr,i)
ans=int(math.Max(float64(ans),float64(lenKmaxSum(rest,k))))
}
returnans
}
funcdelete(arr[]int,indexint)[]int{
len0:=len(arr)-1
ans:=make([]int,len0)
i:=0
forj:=0;jifj!=index{
ans[i]=arr[j]
i++
}
}
returnans
}
funclenKmaxSum(arr[]int,kint)int{
n:=len(arr)
ans:=math.MinInt32
fori:=0;i<=n-k;i++{
cur:=0
forj,cnt:=i,0;cntcur+=arr[j]
}
ans=int(math.Max(float64(ans),float64(cur)))
}
returnans
}
funcmaxSum2(arr[]int,kint)int{
n:=len(arr)
ifn<=k{
return0
}
window:=make([]int,n)
l,r:=0,0
varsumint64=0
ans:=math.MinInt32
fori:=0;iforl=arr[i]{
r--
}
window[r]=i
r++
sum+=int64(arr[i])
ifi>=k{
ans=int(math.Max(float64(ans),float64(sum-int64(arr[window[l]]))))
ifwindow[l]==i-k{
l++
}
sum-=int64(arr[i-k])
}
}
returnans
}
funcrandomArray(n,vint)[]int{
arr:=make([]int,n)
fori:=0;iarr[i]=rand.Intn(2*v+1)-v
}
returnarr
}
funcmain(){
N:=100
V:=1000
testTimes:=10000
fmt.Println("测试开始")
rand.Seed(time.Now().Unix())
fori:=0;irand.Intn(N)
n:=rand.Intn(N)+1
arr:=randomArray(n,V)
k:=rand.Intn(N)+1
ans1:=maxSum1(arr,k)
ans2:=maxSum2(arr,k)
ifans1!=ans2{
fmt.Println("出错了!")
}
}
fmt.Println("测试结束")
}

c++完整代码如下：

#include
#include
#include
#include
#include
usingnamespacestd;
intlenKmaxSum(constvector&arr,intk);
intmaxSum1(vector&arr,intk){
intn=arr.size();
if(n<=k){
return0;
}
intans=INT_MIN;
for(inti=0;ivectorrest(arr.begin(),arr.end());
rest.erase(rest.begin()+i);
ans=max(ans,lenKmaxSum(rest,k));
}
returnans;
}
intlenKmaxSum(constvector&arr,intk){
intn=arr.size();
intans=INT_MIN;
for(inti=0;i<=n-k;i++){
intcur=0;
for(intj=i,cnt=0;cntcur+=arr[j];
}
ans=max(ans,cur);
}
returnans;
}
intmaxSum2(constvector&arr,intk){
intn=arr.size();
if(n<=k){
return0;
}
vectorwindow(n);
intl=0,r=0;
longlongsum=0;
intans=INT_MIN;
for(inti=0;iwhile(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];
}
}
returnans;
}
voidrandomArray(vector&arr,intn,intv){
arr.resize(n);
for(inti=0;iarr[i]=rand()%(2*v+1)-v;
}
}
intmain(){
constintN=100;
constintV=1000;
constintTEST_TIMES=10000;
cout<<"测试开始"<srand(time(NULL));
for(inti=0;iintn=rand()%N+1;
vectorarr;
randomArray(arr,n,V);
intk=rand()%N+1;
intans1=maxSum1(arr,k);
intans2=maxSum2(arr,k);
if(ans1!=ans2){
cout<<"出错了!"<}
}
cout<<"测试结束"<return0;
}

c完整代码如下：

#include
#include
#include
#include
#defineint64_tlonglong
int64_tmax0(int64_ta,int64_tb){
return(a>b)?a:b;
}
int64_tlenKmaxSum(int64_t*arr,int64_tsize,int64_tk);
int64_tmaxSum1(int64_t*arr,int64_tsize,int64_tk){
if(size<=k){
return0;
}
int64_tans=LLONG_MIN;
for(int64_ti=0;iint64_t*rest=malloc((size-1)*sizeof(int64_t));
int64_trestIndex=0;
for(int64_tj=0;jif(j!=i){
rest[restIndex]=arr[j];
restIndex++;
}
}
ans=max0(ans,lenKmaxSum(rest,size-1,k));
free(rest);
}
returnans;
}
int64_tlenKmaxSum(int64_t*arr,int64_tsize,int64_tk){
int64_tans=LLONG_MIN;
for(int64_ti=0;i<=size-k;i++){
int64_tcur=0;
for(int64_tj=i,cnt=0;cntcur+=arr[j];
}
ans=max(ans,cur);
}
returnans;
}
int64_tmaxSum2(int64_t*arr,int64_tsize,int64_tk){
if(size<=k){
return0;
}
int64_t*window=malloc(size*sizeof(int64_t));
int64_tl=0,r=0;
int64_tsum=0;
int64_tans=LLONG_MIN;
for(int64_ti=0;iwhile(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);
returnans;
}
voidrandomArray(int64_t*arr,int64_tsize,int64_tv){
for(int64_ti=0;iarr[i]=rand()%(2*v+1)-v;
}
}
intmain(){
constint64_tN=100;
constint64_tV=1000;
constint64_tTEST_TIMES=10000;
printf("测试开始\n");
srand(time(NULL));
for(int64_ti=0;iint64_tn=rand()%N+1;
int64_t*arr=malloc(n*sizeof(int64_t));
randomArray(arr,n,V);
int64_tk=rand()%N+1;
int64_tans1=maxSum1(arr,n,k);
int64_tans2=maxSum2(arr,n,k);
if(ans1!=ans2){
printf("出错了!\n");
}
free(arr);
}
printf("测试结束\n");
return0;
}