AcWing 135. 最大子序和(Java)
原题链接
简单
作者:
peilin
,
2020-07-08 01:14:26
,
所有人可见
,
阅读 878
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
int[] sums = new int[n+1];
sums[0] = 0;
for(int i = 1; i <= n; i++) {
sums[i] = sums[i-1] + scanner.nextInt();
}
Deque<Integer> deque = new ArrayDeque<>();
deque.offerLast(0);
int ans = Integer.MIN_VALUE;
for(int i = 1; i <= n; i++) {
if(deque.isEmpty()) deque.offerLast(i);
else {
if(i - deque.peekFirst() > m) {
deque.removeFirst();
}
ans = Math.max(ans, sums[i] - sums[deque.peekFirst()]);
while(!deque.isEmpty() &&sums[deque.peekLast()] >= sums[i]) {
deque.pollLast();
}
deque.offerLast(i);
}
}
System.out.println(ans);
}
}