Max Subarray Sum :
Difficulty Level : Easy
Submissions : 145
Asked In :
Marks :10
: 0 | : 0
Given an array of integers, find the subarray with the maximum sum, and output it's sum.
A subarray is a contiguous segment of an array.
Input
First line contains N, the size of the array. (1<= N <=1e5)
Next line contains N space separated integers Ai, (-1e4<= Ai <=1e4)
Output
Output a Single Integer, the sum of the subarray with maximum sum.
Example
Input
9 -2 1 -3 4 -1 2 1 -5 4
Output
6
Note
The subarray [4 -1 2 1] will have the max sum, that is 6.
