 65

# Maximum Subarray Sum

Difficulty: HARD Contributed By
Achint Narang
Avg. time to solve
35 min
Success Rate
81%

Problem Statement
Suggest Edit

#### A subarray is a contiguous segment of an array. In other words, a subarray can be formed by removing 0 or more integers from the beginning, and 0 or more integers from the end of an array.

##### Note :
``````The sum of an empty subarray is 0.
``````
##### Input Format :
``````The first line of input contains an integer N, representing the length of the array.

The second line of input contains N single space-separated integers, denoting the elements of the array.
``````
##### Output Format :
``````In the only output line, output the maximum subarray sum.
``````
##### Note :
``````You are not required to print the output explicitly, it has already been taken care of. Just implement the function.
``````
##### Constraints :
``````1 <= N <= 10^6
-10^6 <= A[i] <= 10^6

where N is the length of the array.
A[i] represents the numbers present in the array.

Time limit: 1sec
``````
##### Sample Input 1 :
``````9
1 2 7 -4 3 2 -10 9 1
``````
##### Sample Output 1 :
``````11
``````
##### Explanation for Sample 1 :
``````The subarray yielding maximum sum is [1, 2, 7, -4, 3, 2].
``````
##### Sample Input 2 :
``````6
10 20 -30 40 -50 60
``````
##### Sample Input 2 :
``````60
``````   Console