Last Updated: 13 Nov, 2020
Maximum Subarray Sum
Moderate
Asked in companies
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(contiguous) 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].
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
Approaches
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.
We will iterate through all possible subarrays of the array with the help of two nested loops. We will maintain the maximum subarray sum/answer through our iterations and finally return it.
The algorithm will be-
- We will run a loop for the starting index of the subarray.
- From every starting index, we will run a loop for the ending index of the subarray.
- We will maintain a variable ‘currSum’ for the sum of the current subarray.
- Let the current ending index be ‘currIndex’. Then for each iteration, we will add ARR[currIndex] to currSum.
- The maximum value of the variable ‘currSum’ encountered will be our answer.
The main observation here is that the optimal subarray will have no prefix with a negative sum. This is because we can remove the prefix with a negative sum from our optimal subarray which will only increase our subarray sum/answer.
The algorithm will be -
- We will iterate through the array. We will maintain the variable ‘currSum’ denoting the maximum sum of prefix elements. Let the current index be ‘currIndex’.
- For each iteration, we will-
- Add ARR[currIndex] to currSum.
- If currSum becomes negative, we will set the value of currSum to 0.
- The maximum value of the variable ‘currSum’ encountered will be our answer.