Maximum Subarray Sum

Posted: 3 Aug, 2020
Difficulty: Hard


Try Problem

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.
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
Approach 1

Let us check for all possible subarrays of the array. For this, we run two loops, where the outer loop points to the left boundary and the inner loop points to the outer boundary of the subarray. 

Using another loop inside, find the sum of this subarray. Compare it with the maximum subarray sum obtained so far. After checking all the subarrays, simply return the maximum sum found.

Try Problem