EN
RU
ES
ZH
FR
DE
PT
AR
HI
Maximum sum of a subarray with cyclic shift
PHP
Hard
arrays
Task «Maximum sum of a subarray with cyclic shift»
Given an array of integers, find the maximum sum of a subarray (contiguous sequence of elements) after applying exactly one cyclic left shift by an arbitrary number of positions (from 0 to N-1). If after the shift the subarray can be empty, the sum of an empty subarray is considered 0. The subarray must contain at least one element if all elements are negative. Constraints: array length from 1 to 10^5, elements from -10^9 to 10^9.
Input Format
The first line contains an integer N (1 ≤ N ≤ 100000) — the size of the array. The second line contains N integers — the elements of the array.
Output Format
One integer — the maximum sum of a subarray after one cyclic left shift.
Examples
Example 1
INPUT
5
OUTPUT
10
Example 2
INPUT
-3
OUTPUT
-6
main.php