Maximum Subarray Sum
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

Question

Maximum Subarray Sum

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

Accepted Answer

I explained him first brute force algorithm, which was to generate all sub arrays of array and then find sum from all these with picking the maximum sum from all. Interviewer was not satisfied and he asks for an optimized approach. I then explain him the kadane's algorithm with an example and he was satisfied with the approach and the example given by me.

Accepted Answer

Brute Force Approach

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.

Space Complexity: O(1)Explanation:

O(1), as constant extra space is required.

Time Complexity: O(n^3)Explanation:

O(N^3), where N is the length of the array.

There are N*(N+1)/2 subarrays in total, and for each subarray, we find its sum in O(N) time.

Accepted Answer

Boundary Fix Approach

According to the previous approach, let us fix the left boundary of the subarray in the outer loop. In the inner loop, we move our right boundary by one unit, every time.

Let’s say for a particular subarray, we have computed its sum. Now when we move the right boundary by one unit, instead of recomputing the sum for the new subarray all over again, we can simply add the value of the new element to the sum of the previous subarray.

In this way, we can reduce our time complexity by remembering the previous result.

Space Complexity: O(1)Explanation:

O(1), as constant extra space is required.

Time Complexity: O(n^2)Explanation:

O(N^2), where N is the length of the array.

There are N*(N+1)/2 subarrays in total, and using the results for the previous subarray, we can compute the sum for the new subarray in O(1) time now.

Accepted Answer

Divide And Conquer Approach

Divide the array into 2 halves.
Get the answer of left and right parts of the array by recursion.
Get the answer of Maximum subarray sum such that the subarray crosses the midpoint.
To find the maximum subarray sum of crossing points we need to find the maximum sum starting from mid point and ending at some point on the left of mid, then find the maximum sum starting from mid + 1 and ending with some point on right of mid + 1. Total sum would be the sum of both left part and right part.
Maximum of all three sums would be the final answer.

Space Complexity: O(n)Explanation:

O(N), where N is the length of the array.

The stack space is used for recursion.

Time Complexity: O(nlogn)Explanation:

O(N*logN), where N is the length of the array.

Because we are dividing our array to two subarrays and in each call for calculating the crossing sum through mid it is taking O(n) time.

T(n) = 2T(n/2) + O(n)

Thus, T(n) = O(nlogn)

Accepted Answer

Sum Array Approach

Let us start from the left of the array. We maintain an array curSum[], which keeps track of the maximum sum of the subarray ending at the index we’re at.

While traversing the array, If the value of curSum[i] becomes negative, we can simply discard this part of the array because it has a negative contribution to the subarray sum. It would be better to just drop that part and have a zero contribution rather than a negative one. Then, we can start anew with the next element. In other words, curSum[i] can be reset to 0.

The maximum value in the curSum array will be our answer.

Space Complexity: O(n)Explanation:

O(N), where N is the length of the array.

Maintaining the curSum array takes O(N) space.

Time Complexity: O(n)Explanation:

O(N), where N is the length of the array.

Traversing the array once takes O(N) time.

Accepted Answer

Inplace Approach

Looking at the previous approach,we realize that to compute curSum[i], we only require the value of curSum[i-1]. Hence, instead of maintaining a whole array, we can simply keep track of the previous value only.

Space Complexity: O(1)Explanation:

O(1), as constant extra space is required.

Time Complexity: O(n)Explanation:

O(N), where N is the length of the array.

Traversing the array once takes O(N) time.

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 :

Input Format :

Output Format :

Note :

Constraints :

Top Nagarro Software Developer Intern interview questions & answers

Popular interview questions of Software Developer Intern

Top HR questions asked in Nagarro Software Developer Intern