 New update is available. Click here to update.

# Maximum Subarray Sum

Contributed by
Achint Narang
Medium 0/80
Avg time to solve 35 mins
Success Rate 81 % Share 707 upvotes

## Problem Statement

#### 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.
``````
Detailed explanation ( Input/output format, Notes, Images ) ##### 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
``````
##### Sample Input 3 :
``````3
-3 -5 -6
``````
##### Sample Input 3 :
``````0
``````  Auto Console