길이 l의 수열 [B_1, B_2, \cdots, B_l]에 대해, 수열의 연속 구간은 [B_i, B_{i+1}, \cdots , B_j]와 같이 수열 위에서 연속적으로 등장하는 수들의 부분 수열로 정의된다.

연속 구간은 비어 있을 수 없다. 즉, 1 ≤ i ≤ j ≤ l을 만족해야 한다.

길이 l의 수열 [B_1, B_2, …. , B_l]에 대해, 수열의 최대 연속 구간 합은 수열의 모든 연속 구간의 원소의 합의 최댓값으로 정의된다.

예를 들어, 수열 [6,-7,3, -1,5, 2]의 최대 연속 구간 합은 9이며, 이는 연속 구간 [3, -1, 5, 2]를 골라서 얻을 수 있다.

수열 B의 최대 연속 구간 합을 수학 기호로 표현하면 max_{1 \le i \le j \le l}(\sum^{j}_{k=i} B_k)이다.

길이 N의 수열 [A_1, A_2, \cdots, A_N]과 Q 개의 쿼리가 주어진다.

i 번째 쿼리는 하나의 정수 X_i로 표현된다. X_i가 주어졌을 때, 수열 [A_1 +X_i, A_2 + X_i, ... ,A_N + X_i]의 최대 연속 구간 합을 계산하라.

수열과 쿼리 timer 3s memory 1024MB

수열과 쿼리 3s 1024MB