Maximum Subarray Sum

Moderate

0/80

13 upvotes

Asked in companies

Problem statement

You are given an array/list ARR consisting of N integers. Your task is to find the maximum possible sum of a non-empty subarray(contagious) of this array.

Note: An array C is a subarray of array D if it can be obtained by deletion of several elements(possibly zero) from the beginning and the end of array D.

For e.g.- All the non-empty subarrays of array [1,2,3] are [1], [2], [3], [1,2], [2,3], [1,2,3].

Detailed explanation ( Input/output format, Notes, Images )

Input Format

The first line of input contains a single integer ‘N’ denoting the number of elements in the array/list.

The second line of input contains ‘N’ single space-separated integers, denoting the elements of the array.

Output Format :

Print the maximum possible sum of any subarray of the array/list. 

Note: You do not need to print anything; it has already been taken care of. Just implement the given function.

Constraints:

1 <= N <= 5*10^5
-10^9 <= ARR[i] <=10^9

Time Limit: 1sec

Sample Input 1 :

4 
2 -7 -11 13

Sample Output 1:

Explanation for Sample 1:

The maximum sum subarray has index range [3, 3].

Sample Input 2 :

5
6 -1 3 -4 3

Sample Output 2 :

Explanation for Sample 2:

The maximum sum subarray has index range [0, 2].

Hint 1

Hint 2

Hint 3

Iterate over all possible subarrays and return the maximum possible sum

Approaches (3)

Approach 1

Approach 2

Approach 3

Brute Force

We will iterate through all possible boundaries of the subarrays in the given array with the help of two nested loops.

Then, we will iterate through each subarray with the help of another loop and find the sum of the subarray. We will maintain the maximum subarray sum through our iterations and finally return it.

Time Complexity

O(N^3), where N denotes the number of elements in an array.

As there are N*(N+1)/2 subarrays in total, and we are iterating over every subarray in linear time, the overall time complexity will be O(N^3).

Space Complexity

O(1), constant space is used.

(100% EXP penalty)

Maximum Subarray Sum

Console