Cracking the coding interview: Smallest sum contiguous subarray — 10

Given an array arr[] of N integers. Find the contiguous sub-array(containing at least one number) which has the minimum sum and return its sum.

Example 1:

Input: 
arr[] = {3,-4, 2,-3,-1, 7,-5}
Output: -6
Explanation: sub-array which has smallest 
sum among all the sub-array is {-4,2,-3,-1} = -6

Example 2:

Input:
arr[] = {2, 6, 8, 1, 4}
Output: 1
Explanation: sub-array which has smallest
sum among all the sub-array is {1} = 1

Your Task:
You don’t need to read input or print anything. The task is to complete the function smallestSubarraySum() which takes arr[] and N as input parameters and returns the sum of subarray with minimum sum.

Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)

Constraints:
1 ≤ N ≤ 106
-107 ≤ A[i] ≤ 107

Solution:
In this question, Kadane’s algorithm is an ideal solution for searching for the maximum sum of a contiguous subarray in an array. How it works is to calculate the maximum subarray pausing at the previous position, but simply breaking down it into a smaller issue. Similarly, it could be considered as a technique of dynamic programming.

Time complexity: O(N)
Space complexity: O(1)