算法至美

用户名：uq_54514514336

访问量：7745

签　名：

等　　级
排　　名	1355
经　　验	2950
参赛次数	0
文章发表	43
年　　龄	0
在职情况	学生
学　　校
专　　业

　　自我简介：

TA的其他文章

信息学奥赛一本通T1177-奇度单增序列-题解（各语言代码）
浏览：345

信息学奥赛一本通T1173-阶乘和-题解（各语言代码）
浏览：239

信息学奥赛一本通T1234-2011-题解（各语言代码）
浏览：597

你可能喜欢

信息学奥赛一本通T1598-最大连续和-题解（各语言代码）

　　作者: 算法至美　　　　发表时间：2022-06-03 19:55:01 浏览：307　|　评论：0　

原题链接：信息学奥赛一本通T1598-最大连续和

题意为求区间和的最大值
可分为两步解决：第一步求区间和，第二步求区间最大值
区间求和最高效的方式是前缀和，而区间最值可以用单调队列解决
时间复杂度O(n)，空间复杂度O(m)
**C++**
```cpp
#include<deque>
#include<iostream>
using namespace std;
int main(){
	ios::sync_with_stdio(false);
	int n,m,s=0,t,r=~0x7fffffff;
	cin>>n>>m;
	for(deque<pair<int,int> >d(1,make_pair(0,n));n--;d.push_back(make_pair(s,n))){
		cin>>t;
		r=max(r,(s+=t)-d.front().first);
		if(d.front().second==n+m)d.pop_front();
		d.resize(lower_bound(d.begin(),d.end(),make_pair(s,n))-d.begin());
	}
	cout<<r;
}
```
**python**
```python
from collections import deque
from itertools import accumulate
m=int(input().split()[1])
d=deque(((-1,0),))
def f(x):
	r=d[0][1]
	if m+d[0][0]==x[0]:d.popleft()
	while d and d[-1][1]>=x[1]:d.pop()
	d.append(x)
	return x[1]-r
print(max(map(f,enumerate(accumulate(map(int,input().split()))))))
```
**java**
```java
import java.util.Deque;
import java.util.Scanner;
import java.util.LinkedList;
import java.util.stream.IntStream;
import java.util.AbstractMap.SimpleEntry;
public class Main {
	public static void main(String[] args) {
		final Scanner in = new Scanner(System.in);
		final int n = in.nextInt(), m = in.nextInt();
		final Deque<SimpleEntry<Integer, Integer>> d = new LinkedList<>();
		d.offer(new SimpleEntry<>(-1, 0));
		System.out.print(IntStream.range(0, n).map(i -> {
			final int p = d.peekLast().getValue() + in.nextInt(), q = d.peek().getValue();
			if (d.peek().getKey() + m == i)
				d.poll();
			while (!d.isEmpty() && d.getLast().getValue() >= p)
				d.pollLast();
			d.offer(new SimpleEntry<>(i, p));
			return p - q;
		}).max().getAsInt());
		in.close();
	}
}
```
**C**
```c
#include<stdio.h>
#include<stdlib.h>
int main(){
	int n,m,r=~0x7fffffff;
	scanf("%d%d",&n,&m);
	int*a=(int*)malloc(sizeof(int)*-~n),*i=a+1,*j=i+n,**b=(int**)malloc(sizeof(int*)*-~n),**x=b,**y=x+1;
	for(*(*b=a)=0;i!=j;*y++=i++){
		scanf("%d",i);
		*i+=*(i-1);
		if(*i-**x>r)r=*i-**x;
		if(*x+m==i)++x;
		while(x!=y&&**(y-1)>=*i)--y;
	}
	printf("%d",r);
	free(b);
	free(a);
}
```
**python**
```python
from collections import deque
from itertools import accumulate
print(max(map((lambda m,d:lambda x:(x[1]-d[0][1],m+d[0][0]==x[0] and d.popleft(),(lambda f:f(f))(lambda f:lambda:d and d[-1][1]>=x[1] and (d.pop(),f(f)()))(),d.append(x))[0])(int(input().split()[1]),deque(((-1,0),))),enumerate(accumulate(map(int,input().split()))))))
```

0.0分

7 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

算法至美

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题7.1 （C语言代码）

C语言程序设计教程（第三版）课后习题8.7 （C语言代码）

蛇行矩阵（C语言代码）

不容易系列2 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

信息学奥赛一本通T1598-最大连续和-题解（各语言代码）

评论区

精彩推荐

【亲和数】（C语言代码）

C语言程序设计教程（第三版）课后习题6.10 （C语言代码）

WU-拆分位数（C++代码）

【计算两点间的距离】（C语言代码）

用筛法求之N内的素数。（C++代码）

C语言训练-自由落体问题（C语言代码）

打印十字图（C语言代码）

复数求和（C语言代码）

整数平均值（C语言代码）

上车人数（C语言代码）

算法至美

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题7.1 （C语言代码）

C语言程序设计教程（第三版）课后习题8.7 （C语言代码）

蛇行矩阵 （C语言代码）

不容易系列2 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

信息学奥赛一本通T1598-最大连续和-题解（各语言代码）

评论区

精彩推荐

【亲和数】 （C语言代码）

C语言程序设计教程（第三版）课后习题6.10 （C语言代码）

WU-拆分位数 （C++代码）

【计算两点间的距离】 （C语言代码）

用筛法求之N内的素数。 （C++代码）

C语言训练-自由落体问题 （C语言代码）

打印十字图 （C语言代码）

复数求和 （C语言代码）

整数平均值 （C语言代码）

上车人数 （C语言代码）

蛇行矩阵（C语言代码）

　　评论区

【亲和数】（C语言代码）

WU-拆分位数（C++代码）

【计算两点间的距离】（C语言代码）

用筛法求之N内的素数。（C++代码）

C语言训练-自由落体问题（C语言代码）

打印十字图（C语言代码）

复数求和（C语言代码）

整数平均值（C语言代码）

上车人数（C语言代码）