New update is available. Click here to update.

Solve problems & track your progress

Checkout your overall progress in every topic here

Become

Sensei

in DSA topics

Open the topic and solve more problems associated with it to improve your skills

Check out the skill meter for every topic

See how many problems you are left with to solve for cracking any stage. Score more than zero to get your progress counted.

Problem

Submissions

Maximum Subarray Sum

Contributed by

Achint Narang

Medium

0/80

Avg time to solve 35 mins

Success Rate 81 %

707 upvotes

Problem Statement

You are given an array (ARR) of length N, consisting of integers. You have to find the sum of the subarray (including empty subarray) having maximum sum among all subarrays.

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 )

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 :

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 :

Sample Input 3 :

3
-3 -5 -6

Sample Input 3 :

Auto

Console