AcWing 135. 【java】最大子序和
原题链接
简单
作者:
tt2767
,
2019-12-09 00:36:08
,
所有人可见
,
阅读 913
import java.util.*;
public class Main{
void run(){
int n = jin.nextInt();
int m = jin.nextInt();
nums.add(0);
for (int i = 0 ; i < n ; i++) nums.add(jin.nextInt());
for (int i = 1 ; i <= n ; i++) nums.set(i, nums.get(i)+nums.get(i-1));
int res = Integer.MIN_VALUE;
for (int i = 1; i <= n ; i++){
while(!queue.isEmpty() && i - queue.peekFirst() > m) queue.removeFirst();
if (!queue.isEmpty()) res = Math.max(res, nums.get(i) - nums.get(queue.peekFirst())); // why not peekF -1 ?
else res = Math.max(res, nums.get(i)); // 差点漏掉了
while(!queue.isEmpty() && nums.get(i) <= nums.get(queue.peekLast())) queue.removeLast();
queue.offerLast(i);
}
res = Math.max(res, nums.get(n) - nums.get(queue.peekFirst()-1));
System.out.println(res);
}
List<Integer> nums = new ArrayList<>();
Deque<Integer> queue = new LinkedList<>();
private Scanner jin = new Scanner(System.in);
public static void main(String[] args) throws Exception {new Main().run();}
}