/Max-Subarray

The maximum subarray problem is the task of finding the contiguous subarray within a one-dimensional array, a[1...n], of numbers which has the largest sum. This script solves the max subarray problem via divide-and-conquer with O(nlogn) time complexity.

Primary LanguageC++

Max Subarray

Author: @037

Compile

sudo g++ -std=c++11 -o MaxSubarray.exe MaxSubarray.cpp

Input structure

The input starts with an integer numbern, which indicates the array size.Then, the integers, A[1], A[2], ... , A[n], follow, one per line.

Output structure

Output the sum of integers in the max subarray, i.e., A[i*] + A[i* + 1] + ... + A[j*].

Example

Input

6
-3
11
-2
-3
10
-5

Output

16