Last Updated: 30 Dec, 2020
Minimum Sum Subarray
Easy
Asked in companies
You have been given an array/list 'ARR' consisting of 'N' integers.
Your task is to find the minimum possible sum of a non-empty subarray 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 example, all the non-empty subarrays of array [1,2,3] are [1], [2], [3], [1,2], [2,3], [1,2,3].
For Example :
Input: 'N' = 3 , 'ARR' = [-5, 10 , 0]
Output: -5
Explanation : The non empty subarrays possible for 'ARR' are [-5], [10], [0], [-5, 10], [-5, 0], [10, 0], [-5, 10, 0]. The sum of the elements of these subarrays are -5, 10, 0, 5, -5, 10, 5. The minimum of them is -5.
Input Format
The first line of input contains an integer 'T' which denotes the number of test cases or queries to be run. Then the test cases follow.
The first line of each test case contains a single integer ‘N’ denoting the number of elements in the array/list.
The second line of each test case contains ‘N’ single space-separated integers, denoting the elements of the array/list.
Output Format :
For each test case, return the minimum 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 <= T <= 100
1 <= N <= 5000
-10^5 <= ARR[i] <=10^5
Time Limit : 1 second
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 that subarray. We will maintain the minimum subarray sum through our iterations and finally return it.
Unlike the previous approach, we will iterate through all possible subarrays of the array and calculate their sum with the help of two nested loops only. We will maintain the minimum subarray sum/answer through our iterations and finally return it.
Here is the algorithm:
- 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 'CURR_SUBARRAY_SUM' for the sum of the current subarray.
- Let the current ending index be ‘i’. Then for each iteration, we will add ‘ARR[i]’ to 'CURR_SUBARRAY_SUM'.
- The minimum value of the variable 'CURR_SUBARRAY_SUM' encountered will be our answer.
The main observation here is that the optimal subarray will have no prefix with a positive-sum. This is because we can remove the prefix with a positive-sum from our optimal subarray, which will only increase our subarray sum/answer.
Here is the algorithm:
- We will iterate through the array. We will maintain the variable 'CURR_SUBARRAY_SUM' denoting the minimum sum of prefix elements. Let the current index be ‘i'.
- For each iteration, we will-
- Add ‘ARR[i]’ to 'CURR_SUBARRAY_SUM.
- If 'CURR_SUBARRAY_SUM' becomes greater than ‘ARR[i]’, we will set the value of 'CURR_SUBARRAY_SUM' to ‘ARR[i]’.
- The minimum value of the variable 'CURR_SUBARRAY_SUM' encountered will be our answer.