Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding
Ninjas X Naukri.com

Last Updated: 30 Dec, 2020

Easy

```
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].
```

```
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.
```

```
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.
```

```
For each test case, return the minimum possible sum of any subarray of the array/list.
```

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

```
1 <= T <= 100
1 <= N <= 5000
-10^5 <= ARR[i] <=10^5
Time Limit : 1 second
```

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'
- Let the current ending index be ‘
*i’.*Then for each iteration, we will add ‘*ARR[i]’*to 'CURR_SUBARRAY_SUM'.

- We will maintain a variable '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'
*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*]’.

- Add ‘
- The minimum value of the variable 'CURR_SUBARRAY_SUM' encountered will be our answer.

Similar problems