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 ≤ 10^{6}
-10^{7} ≤ A[i] ≤ 10^{7}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Dynamic programming

Data structures

Starter code: #User function Template for python3





class Solution:

    def smallestSumSubarray(self, A, N):

        #Your code here

Solutions:
class Solution:

	def smallestSumSubarray(self, A, N):
		cur_sum = 0
		mini = 243131654
		for i in range(N):
			cur_sum = cur_sum + A[i]
			if cur_sum < mini:
				mini = cur_sum
			if cur_sum > 0:
				cur_sum = 0
		return mini


class Solution:

	def smallestSumSubarray(self, A, N):
		mini = float('inf')
		cur = A[0]
		for i in A[1:]:
			if i > 0:
				mini = min(mini, cur)
				if i < mini:
					mini = i
					cur = i
				else:
					cur += i
			else:
				if cur > 0:
					cur = 0
				cur += i
		return min(mini, cur)


import math

class Solution:

	def smallestSumSubarray(self, arr, n):
		local_min = 0
		global_min = math.inf
		for ele in arr:
			local_min += ele
			global_min = min(local_min, global_min)
			if local_min > 0:
				local_min = 0
		return global_min


class Solution:

	def smallestSumSubarray(self, A, N):
		min_sum = A[0]
		current_sum = A[0]
		for i in range(1, N):
			current_sum = min(A[i], current_sum + A[i])
			min_sum = min(min_sum, current_sum)
		return min_sum


class Solution:

	def smallestSumSubarray(self, a, n):
		ans = 1000000000
		sm = 0
		for i in range(n):
			sm += a[i]
			ans = min(ans, sm, a[i])
			if sm > 0:
				sm = 0
		return ans


import sys

class Solution:

	def smallestSumSubarray(self, A, N):
		mina = sys.maxsize
		temp = 0
		for i in A:
			temp = temp + i
			if temp < mina:
				mina = temp
			if temp > 0:
				temp = 0
		return mina


class Solution:

	def smallestSumSubarray(self, a, n):
		ans = 1000000000
		sm = 0
		j = 0
		for i in range(n):
			el = a[i]
			sm += el
			ans = min(ans, sm, el)
			if sm > 0:
				while sm > 0 and j < i:
					sm -= a[j]
					ans = min(ans, sm, el)
					j += 1
			if sm > 0:
				sm = 0
				j = i + 1
		return ans


class Solution:

	def smallestSumSubarray(self, A, N):
		a = A[0]
		b = A[0]
		for i in range(1, N):
			b = min(A[i], b + A[i])
			a = min(a, b)
		return a


class Solution:

	def smallestSumSubarray(self, A, N):
		prefixSumList = [0] * N
		prevSum = 0
		index = 0
		while index < N:
			curElement = A[index]
			if curElement + prevSum <= curElement:
				prefixSumList[index] = curElement + prevSum
			else:
				prefixSumList[index] = curElement
			prevSum = prefixSumList[index]
			index += 1
		return min(prefixSumList)


class Solution:

	def smallestSumSubarray(self, A, N):
		start = 0
		end = 0
		min_summ = 999999
		summ = 0
		while end < N and start <= end:
			summ += A[end]
			min_summ = min(min_summ, summ)
			if summ > 0:
				start = end + 1
				summ = 0
			end += 1
		return min_summ


class Solution:

	def smallestSumSubarray(self, A, N):
		min_so_far = pow(2, 32)
		min_till_here = 0
		for i in A:
			min_till_here += i
			min_so_far = min(min_so_far, min_till_here)
			if min_till_here > 0:
				min_till_here = 0
		return min_so_far


class Solution:

	def smallestSumSubarray(self, arr, n):
		sum = 0
		min = 10 ** 9
		for ele in arr:
			sum += ele
			if min > sum:
				min = sum
			if sum > 0:
				sum = 0
		return min


class Solution:

	def smallestSumSubarray(self, A, N):
		min_sum = 100000000.0
		sum = 0
		for i in range(N):
			sum = sum + A[i]
			if sum < min_sum:
				min_sum = sum
			if sum >= 0:
				sum = 0
		return min_sum


class Solution:

	def smallestSumSubarray(self, A, N):
		currSum = 0
		minSum = A[0]
		for i in range(N):
			currSum += A[i]
			minSum = min(minSum, currSum)
			if currSum > 0:
				currSum = 0
		return minSum


class Solution:

	def smallestSumSubarray(self, arr, n):
		mini = arr[0]
		sum1 = 0
		for i in range(n):
			sum1 += arr[i]
			mini = min(mini, sum1)
			if sum1 > 0:
				sum1 = 0
		return mini


class Solution:

	def smallestSumSubarray(self, A, N):
		dp = [0] * (N + 1)
		sol = float('inf')
		for (i, x) in enumerate(A):
			dp[i] = t = x + min(dp[i - 1], 0)
			if t < sol:
				sol = t
		return sol


class Solution:

	def smallestSumSubarray(self, A, N):
		overall_min = A[0]
		current_min = A[0]
		for i in range(1, N):
			current_min = min(A[i], current_min + A[i])
			overall_min = min(overall_min, current_min)
		return overall_min


class Solution:

	def smallestSumSubarray(self, A, N):
		arr = A
		n = N
		dp = [None] * (n + 1)
		sol = float('inf')
		dp[n] = float('inf')
		for (i, x) in enumerate(arr):
			dp[i] = min(x, x + dp[i - 1])
			sol = min(sol, dp[i])
		return sol


class Solution:

	def smallestSumSubarray(self, A, N):
		minsum = float('inf')
		total = 0
		for i in range(N):
			total += A[i]
			minsum = min(total, minsum)
			if total > 0:
				total = 0
		return minsum


class Solution:

	def smallestSumSubarray(self, A, N):
		mini = A[0]
		res = A[0]
		for i in range(1, N):
			mini = min(mini + A[i], A[i])
			res = min(mini, res)
		return res


class Solution:

	def smallestSumSubarray(self, A, N):
		total = sum(A)
		curSum = A[0]
		minSum = A[0]
		for i in range(1, N):
			if curSum > 0:
				curSum = A[i]
			else:
				curSum += A[i]
			minSum = min(minSum, curSum)
		return minSum


class Solution:

	def smallestSumSubarray(self, a, n):
		s = 0
		m = -999999
		ans = 9999999
		for i in range(n):
			ans = min(a[i], ans)
			s += a[i]
			ans = min(s, ans)
			if m < s:
				m = s
			else:
				ans = min(s - m, ans)
		return ans


class Solution:

	def smallestSumSubarray(self, A, N):
		minval = min(A)
		currsum = 0
		for i in A:
			currsum += i
			minval = min(minval, currsum)
			if currsum > 0:
				currsum = 0
		return minval


class Solution:

	def smallestSumSubarray(self, A, N):
		ans = min(A)
		(i, j) = (0, 0)
		sum1 = 0
		while j < len(A):
			sum1 += A[j]
			if sum1 < 0:
				while A[i] >= 0:
					sum1 -= A[i]
					i += 1
				ans = min(ans, sum1)
				j += 1
			else:
				while i < j:
					sum1 -= A[i]
					i += 1
				j += 1
		return ans


class Solution:

	def smallestSumSubarray(self, A, N):
		sm = mn = 0
		least_positive = 10 ** 9
		for i in A:
			sm += i
			if sm >= 0:
				sm = 0
			else:
				mn = min(mn, sm)
			if i >= 0 and i < least_positive:
				least_positive = i
		return mn if mn != 0 else least_positive


class Solution:

	def smallestSumSubarray(self, A, N):
		s = 0
		p = 999999
		for i in A:
			s += i
			if s < p:
				p = s
			if s > 0:
				s = 0
		return p


class Solution:

	def smallestSumSubarray(self, A, N):
		mini = 999
		su = 0
		for i in A:
			su += i
			mini = min(su, mini)
			if su > 0:
				su = 0
		if len(A) == 1:
			return A[0]
		return mini


class Solution:

	def smallestSumSubarray(self, A, N):
		mini = A[0]
		s = 0
		for i in range(N):
			s = s + A[i]
			mini = min(s, mini)
			if s >= 0:
				s = 0
		return mini


class Solution:

	def smallestSumSubarray(self, A, N):
		curr_min = A[0]
		min_ans = A[0]
		for i in range(1, N):
			curr_min = min(curr_min + A[i], A[i])
			min_ans = min(curr_min, min_ans)
		return min_ans


import sys

class Solution:

	def smallestSumSubarray(self, A, N):
		ans = sys.maxsize
		sum_till = 0
		for i in range(0, N):
			sum_till += A[i]
			ans = min(ans, sum_till)
			if sum_till > 0:
				sum_till = 0
		return ans


class Solution:

	def smallestSumSubarray(self, A, N):
		Sum = A[0]
		arr_sum = Sum
		Arr = [A[0]]
		for i in range(1, N):
			ele = A[i]
			new_s = arr_sum + ele
			if new_s < 0 and new_s < ele:
				Arr.append(ele)
				arr_sum += ele
			else:
				Arr = [ele]
				arr_sum = ele
			if new_s < Sum:
				Sum = new_s
			if ele < Sum:
				Sum = ele
			if arr_sum < Sum:
				Sum = arr_sum
		return Sum


class Solution:

	def smallestSumSubarray(self, A, N):
		curr = A[0]
		maxi = A[0]
		for ele in A[1:]:
			curr = min(ele, curr + ele)
			maxi = min(curr, maxi)
		return maxi


class Solution:

	def smallestSumSubarray(self, A, N):
		for i in range(N):
			A[i] = -1 * A[i]
		meh = 0
		largest = -999999
		for i in A:
			meh = meh + i
			if i > meh:
				meh = i
			if meh > largest:
				largest = meh
		return -1 * largest


from sys import maxsize

class Solution:

	def smallestSumSubarray(self, arr, N):
		minSoFar = arr[0]
		minOverall = arr[0]
		for i in range(1, N):
			minOverall = min(minSoFar, minOverall)
			if minSoFar > 0:
				minSoFar = arr[i]
			else:
				minSoFar += arr[i]
		minOverall = min(minSoFar, minOverall)
		return minOverall


class Solution:

	def smallestSumSubarray(self, arr, n):
		currsum = 0
		minsum = float('inf')
		for i in range(n):
			currsum += arr[i]
			minsum = min(minsum, currsum)
			if currsum >= 0:
				currsum = 0
		return minsum


class Solution:

	def smallestSumSubarray(self, A, N):
		import math
		min_sum = math.inf
		curr_sum = 0
		i = 0
		while i < N:
			curr_sum += A[i]
			if curr_sum < min_sum:
				min_sum = curr_sum
			if curr_sum > 0:
				curr_sum = 0
			i += 1
		return min_sum


class Solution:

	def smallestSumSubarray(self, a, n):
		suk = 0
		mat = sum(a)
		for i in a:
			suk += i
			mat = min(suk, mat)
			if suk > 0:
				suk = 0
		return mat


class Solution:

	def smallestSumSubarray(self, A, N):
		n = len(A)
		mini = float('inf')
		csum = 0
		for i in range(n):
			csum += A[i]
			if csum < mini:
				mini = csum
			if csum > 0:
				csum = 0
		return mini


class Solution:

	def smallestSumSubarray(self, arr, n):
		maxsize = int(1000000000.0 + 7)
		min_ending_here = maxsize
		min_so_far = maxsize
		for i in range(n):
			if min_ending_here > 0:
				min_ending_here = arr[i]
			else:
				min_ending_here += arr[i]
			min_so_far = min(min_so_far, min_ending_here)
		return min_so_far


class Solution:

	def smallestSumSubarray(self, A, N):
		(s, mx) = (0, float('inf'))
		for i in A:
			s += i
			mx = min(s, mx)
			if s > 0:
				s = 0
		return mx


class Solution:

	def smallestSumSubarray(self, a, n):
		minsum = float('inf')
		cmin = 0
		for i in a:
			cmin = min(i, cmin + i)
			minsum = min(minsum, cmin)
		return minsum


class Solution:

	def smallestSumSubarray(self, A, N):
		min_sum = 9999999
		curr_sum = 0
		for i in range(0, N):
			curr_sum = curr_sum + A[i]
			if curr_sum < min_sum:
				min_sum = curr_sum
			if curr_sum > 0:
				curr_sum = 0
		return min_sum


class Solution:

	def smallestSumSubarray(self, A, N):
		if N > 0:
			S = math.inf
			S_aux = S
			idx = 0
			while idx < N:
				if S > 0:
					if A[idx] < S:
						S = A[idx]
						S_aux = S
						last_idx = idx
				else:
					if A[idx] < 0:
						if last_idx == idx - 1:
							S += A[idx]
							last_idx = idx
						elif A[idx] < S:
							S = A[idx]
							last_idx = idx
					if S_aux + A[idx] < 0:
						S_aux += A[idx]
						if S_aux < S:
							S = S_aux
					else:
						S_aux = 0
				idx += 1
		return S


class Solution:

	def smallestSumSubarray(self, A, N):
		minSum = A[0]
		curSum = 0
		for i in range(N):
			curSum += A[i]
			if curSum < minSum:
				minSum = curSum
			if curSum > 0:
				curSum = 0
		return minSum


class Solution:

	def smallestSumSubarray(self, A, N):
		sumi = 0
		mini = A[0]
		for i in range(N):
			if sumi > 0:
				sumi = A[i]
			else:
				sumi += A[i]
			mini = min(mini, sumi)
		return mini


class Solution:

	def smallestSumSubarray(self, arr, N):
		cur = arr[0]
		msum = arr[0]
		for i in range(1, N):
			if msum > 0:
				cur = arr[i]
			else:
				cur = min(cur + arr[i], arr[i])
			msum = min(msum, cur)
		return msum


class Solution:

	def smallestSumSubarray(self, A, N):
		if max(A) < 0:
			return sum(A)
		if min(A) >= 0:
			if min(A) == 0:
				return 0
			else:
				return min(A)
		mini = float('inf')
		curr = 0
		for i in A:
			curr += i
			mini = min(curr, mini)
			if curr > 0:
				curr = 0
		return mini


class Solution:

	def smallestSumSubarray(self, A, N):
		curSum = A[0]
		minSum = A[0]
		for l in range(1, len(A)):
			curSum = min(A[l], curSum + A[l])
			if curSum < minSum:
				minSum = curSum
		return minSum


class Solution:

	def smallestSumSubarray(self, arr, n):
		curr_sum = 0
		min_sum = 999
		for i in range(len(arr)):
			curr_sum += arr[i]
			if curr_sum <= min_sum:
				min_sum = curr_sum
			if curr_sum > 0:
				curr_sum = 0
		if len(arr) == 1:
			return arr[0]
		return min_sum


class Solution:

	def smallestSumSubarray(self, A, N):
		lcmin = A[0]
		glmin = A[0]
		for i in range(1, N):
			lcmin = min(lcmin + A[i], A[i])
			glmin = min(lcmin, glmin)
		return glmin


class Solution:

	def smallestSumSubarray(self, A, N):
		min_sf = A[0]
		mini = A[0]
		for ele in A[1:]:
			min_sf = min(ele, min_sf + ele)
			mini = min(mini, min_sf)
		return mini


class Solution:

	def smallestSumSubarray(self, A, N):
		mini = 1000000000.0
		summ = 0
		for i in A:
			summ += i
			mini = min(mini, summ)
			if summ >= 0:
				summ = 0
		return mini


class Solution:

	def smallestSumSubarray(self, A, N):
		minimum = float('inf')
		su = 0
		for i in range(N):
			su += A[i]
			if minimum > su:
				minimum = su
			if su > 0:
				su = 0
		return minimum


class Solution:

	def smallestSumSubarray(self, A, N):
		sum = 0
		minsum = min(A)
		for i in range(0, N):
			sum = sum + A[i]
			if sum < minsum:
				minsum = sum
			if sum > 0:
				sum = 0
		return minsum


class Solution:

	def smallestSumSubarray(self, arr, n):
		min_sum = arr[0]
		sum1 = arr[0]
		for i in range(1, n):
			sum1 += arr[i]
			min_sum = min(min_sum, arr[i], sum1)
			if arr[i] < sum1:
				sum1 = arr[i]
		return min_sum


class Solution:

	def smallestSumSubarray(self, A, n):
		res = A[0]
		tmp = A[0]
		for i in range(1, n):
			tmp = min(A[i], tmp + A[i])
			res = min(res, tmp)
		return res


class Solution:

	def smallestSumSubarray(self, arr, N):
		cursum = 0
		min = float('inf')
		for i in range(N):
			cursum = cursum + arr[i]
			if cursum < min:
				min = cursum
			if cursum > 0:
				cursum = 0
		return min


class Solution:

	def smallestSumSubarray(self, A, N):
		cursum = 0
		minsum = float('inf')
		for i in A:
			cursum = cursum + i
			if minsum > cursum:
				minsum = cursum
			if cursum > 0:
				cursum = 0
		return minsum


class Solution:

	def smallestSumSubarray(self, A, N):
		curr = A[0]
		miner = A[0]
		for i in range(1, N):
			curr += A[i]
			if curr > A[i]:
				curr = A[i]
			miner = min(miner, curr)
		return miner


class Solution:

	def smallestSumSubarray(self, A, N):
		min_sum_so_far = 0
		min_sum_end_here = float('inf')
		for i in A:
			min_sum_so_far += i
			if min_sum_end_here > min_sum_so_far:
				min_sum_end_here = min_sum_so_far
			if min_sum_so_far > 0:
				min_sum_so_far = 0
		return min_sum_end_here


import sys

class Solution:

	def smallestSumSubarray(self, a, n):
		maxsize = 1000000001
		min_end = maxsize
		max_far = maxsize
		for i in range(n):
			if min_end > 0:
				min_end = a[i]
			else:
				min_end += a[i]
			max_far = min(max_far, min_end)
		return max_far


class Solution:

	def smallestSumSubarray(self, A, N):
		if len(A) == 0:
			return 0
		ans = float('inf')
		min_sum = 0
		for i in range(len(A)):
			min_sum = min(A[i], A[i] + min_sum)
			ans = min(ans, min_sum)
		return ans


class Solution:

	def smallestSumSubarray(self, a, N):
		temp = min1 = float('inf')
		for i in a:
			temp = min(temp + i, i)
			min1 = min(min1, temp)
		return min1


class Solution:

	def smallestSumSubarray(self, A, N):
		A = [-1 * x for x in A]
		cs = 0
		mx = 0
		l = []
		p = 0
		for x in A:
			if x < 0:
				p += 1
			if x + cs > 0:
				cs += x
				l.append(cs)
			else:
				l.append(cs)
				cs = 0
		if p == N:
			return -1 * max(A)
		if p == 0:
			return -1 * sum(A)
		return -1 * max(l)


class Solution:

	def smallestSumSubarray(self, arr, n):
		ans = float('inf')
		curr = 0
		for val in arr:
			ans = min(ans, val)
			if curr + val > 0:
				curr = 0
			else:
				curr += val
				ans = min(ans, curr)
		return ans


class Solution:

	def smallestSumSubarray(self, arr, n):
		(prev_max, prev_min, glob_min) = (arr[0], arr[0], arr[0])
		for i in range(1, n):
			curr_max = max(prev_max + arr[i], prev_min + arr[i], arr[i])
			curr_min = min(prev_max + arr[i], prev_min + arr[i], arr[i])
			glob_min = min(glob_min, curr_min)
			prev_max = curr_max
			prev_min = curr_min
		return glob_min


class Solution:

	def smallestSumSubarray(self, arr, n):
		sumval = 0
		minval = float('inf')
		for num in arr:
			sumval += num
			minval = min(minval, sumval)
			if sumval > 0:
				sumval = 0
		return minval


class Solution:

	def smallestSumSubarray(self, A, N):
		curr = 0
		mini = 1000000000.0
		for i in range(N):
			curr += A[i]
			mini = min(mini, curr)
			if curr > 0:
				curr = 0
		return mini


class Solution:

	def smallestSumSubarray(self, A, N):
		prefix_sum = [A[i] for i in range(N)]
		for i in range(1, N):
			prefix_sum[i] = A[i] + prefix_sum[i - 1]
		ans = prefix_sum[0]
		maxi = max(prefix_sum[0], 0)
		for i in range(1, N):
			ans = min(ans, prefix_sum[i] - maxi)
			maxi = max(maxi, prefix_sum[i], 0)
		return ans


class Solution:

	def smallestSumSubarray(self, A, N):
		currentSum = 0
		minSum = A[0]
		for n in A:
			currentSum += n
			if n < currentSum:
				currentSum = n
			minSum = min(minSum, currentSum)
		return minSum


class Solution:

	def smallestSumSubarray(self, a, n):
		(m1, m2) = (10 ** 9, 10 ** 9)
		for i in range(n):
			m1 = min(m1 + a[i], a[i])
			m2 = min(m1, m2)
		return m2


class Solution:

	def smallestSumSubarray(self, arr, N):
		count = 0
		ans = 9999
		for i in arr:
			count += i
			count = min(count, i)
			ans = min(ans, count)
		return ans


class Solution:

	def smallestSumSubarray(self, arr, N):
		curr = 0
		miniCur = 1000000000.0
		for i in range(N):
			curr += arr[i]
			miniCur = min(miniCur, curr)
			if curr > 0:
				curr = 0
		return miniCur


class Solution:

	def smallestSumSubarray(self, nums, N):
		sum = 0
		maxi = 1000000000.0
		for i in range(len(nums)):
			sum += nums[i]
			maxi = min(maxi, sum)
			if sum >= 0:
				sum = 0
		return maxi