EN
RU
ES
ZH
FR
DE
PT
AR
HI
Search for the maximum subarray sum with a length condition in a circular array
PHP
Hard
loops
Task «Search for the maximum subarray sum with a length condition in a circular array»
Given a cyclic integer array of length N (N ≤ 10^5). Find the maximum sum of a contiguous subarray of length at least L and at most R (1 ≤ L ≤ R ≤ N). The subarray may cross the array boundary (cyclic). Output the required sum. If there are no such subarrays (for example, L > N), output 0.
Input Format
In the first line, an integer N. In the second line, N integers separated by spaces. In the third line, two integers L and R separated by spaces.
Output Format
One integer — the maximum sum of a subarray with length from L to R inclusive. If no such subarray exists, output 0.
Examples
Example 1
INPUT
6
5 -2 3 1 -1 4
1 3
OUTPUT
9
Example 2
INPUT
3
10 -5 10
OUTPUT
20
Example 3
INPUT
5
1 -2 3 -4 5
OUTPUT
8
main.php