# Smallest sum contiguous subarray

#### Algorithms Dynamic Programming (DP)

You are given an array of n integers. The task is to find the sum of the subarray which has the smallest possible sum.

Note: Subarray is an array formed by a block of contiguous elements of the parent ( or original ) array.

## Examples

Input:
No. of elements in the array = 5
Array : -4 3 -1 -6 8
Output:
-8


Explanation: The subarray [-4, 3, -1, -6] gives the minimum sum.

Input:
No. of elements in the array = 5
Array : 3 5 1 2 4
Output:
1


Explanation: The subarray [1] gives the minimum sum.

# Approach

## Algorithm 1 (Brute-force)

We simply iterate over all the possible subarrays, find the sum of elements in each subarray and find the minimum of them.

### Pseudocode

// Using 1-indexing
//array[i] represents the ith element in the input array
ans = INFINITY
for i in 1 to size_of_array:
for j in i to size_of_array:
sum = 0
for k in i to j:
sum += array[k]
ans = min(ans,sum)

print(ans)
The time complexity of this algorithm is O(N3).

## Algorithm 2 (Optimized Brute-force)

For this we remove one loop from Algorithm 1 to increase efficiency. We can calculate the sum at the same time when the end of the subarray moves.

### Pseudocode

// Using 1-indexing
//array[i] represents the ith element in the input array
ans = INFINITY
for i in 1 to size_of_array:
sum = 0
for j in i to size_of_array:
sum += array[j]
ans = min(ans,sum)

print(ans)
The time complexity of this algorithm is O(N2).

## Algorithm 3 (Efficient Approach)

Surprisingly, it is possible to solve the problem in O(N) time, using dynamic programming. The idea is to calculate, for each index : the minimum sum of a subarray that ends at that index.And then the answer will be the minimum of all these sums.
Thus the problem reduces to the subproblem: find the minimum sum of a subarray that ends at the index k. Thus, there are only two possibilities:
1. The subarray only contains the element array[k].
2. The subarray consists of a subarray that ends at position k-1, followed by the element at position k.

Let us denote the the minimum sum of a subarray that ends at the index k by Xk. From the above propositions, we get the relation: Xk = min(array[k], array[k] + Xk-1 )

### Pseudocode

// Using 1-indexing
//array[i] represents the ith element in the input array
ans = INFINITY
sum = 0
for i in 1 to size_of_array:
sum = min(array[i], array[i] + sum)
ans = min(ans, sum)

print(ans)

The time complexity of this algorithm is O(N) and it is the best possible time complexity as we need to go through all the array elements at least once.

### C++

//C++ program to find smallest sum subarray
#include <iostream>
#include <climits>
#include <algorithm>
using namespace std;

//function declaration
int smallestSubarraySum(int a[], int n){

int sum = 0;
int ans = INT_MAX;
for(int i = 0 ; i < n ; ++i){
sum = min(a[i], a[i] + sum);
ans = min(ans, sum);
}

return ans;
}

int main(){
//input
int n;
cout << "No. of elements in the array = ";
cin >> n;
int a[n];
cout << "Array : ";
for(int i = 0 ; i < n ; ++i){
cin >> a[i];
}

//output
cout << smallestSubarraySum(a,n);
return 0;
}


### Time Complexity

• Worst case time complexity: O(N)
• Average case time complexity: Θ(N)
• Best case time complexity: Ω(N)
• Auxiliary space: O(1)
• Space complexity: Θ(N)
where N is the number of elements

TRY IT YOURSELF : Modify the above code to reduce its space complexity to O(1).

## An Interesting Problem

Solve the smallest sum subarray problem using Kadane's algorithm.

## Solution

Kadane's algorithm gives the answer of maximum sum subarray problem ( i.e. sum of the subarray with the maximum sum ). If we replace each array[i] with -array[i] then we apply Kadane's algorithm let's name the output X. Then negative of X will give us the answer of smallest sum subarray problem.

#### Pseudocode

// Using 1-indexing
//array[i] represents the ith element in the input array

for i in 1 to n:
array[i] = -1*array[i]

ans = -INFINITY
sum = 0
for i in 1 to size_of_array:
sum = max(array[i], array[i] + sum)
ans = max(ans, sum)

print(-1*ans)
The time complexity of this algorithm is O(N) (same as Kadane's Algorithm).

### C++

//C++ program to find smallest sum subarray
#include <iostream>
#include <climits>
#include <algorithm>
using namespace std;

int ans = INT_MIN;
int sum = 0;

for(int i = 0 ; i < n ; ++i){
sum = max(a[i], a[i] + sum);
ans = max(ans, sum);
}

return ans;
}

int smallestSubarraySum(int a[], int n){
for(int i = 0 ; i < n ; ++i){
a[i] = -1*a[i];
}

}

int main(){
//input
int n;
cout << "No. of elements in the array = ";
cin >> n;
int a[n];
cout << "Array : ";
for(int i = 0 ; i < n ; ++i){
cin >> a[i];
}

//output
cout << smallestSubarraySum(a,n);
return 0;
}


### Time Complexity

• Worst case time complexity: O(N)
• Average case time complexity: Θ(N)
• Best case time complexity: Ω(N)
• Auxiliary space: O(1)
• Space complexity: Θ(N)
where N is the number of elements

Feel free to share your approach in the discussion thread below. Happy Coding :)