Minimum Sum Subarray

Posted: 30 Dec, 2020
Difficulty: Easy

PROBLEM STATEMENT

Try Problem

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

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.

Try Problem