Smallest Sum Contiguous Subarray in Python

What is Subarray?

Subarray is the slice from the given array which is contiguous(i.e occupy consecutive positions).

It inherently maintains the order of the elements.

Let us take an example to clear the above-stated statement.

a=[1,2,3,4,]

The subarrays of the above-given array are:-

[1],[2],[3],[4],[1,2] and so on.

Now get to our task i.e we have to find the Smallest Sum Contiguous Subarray in Python

So to do this there are many algorithms but we are going to use the opposite of Kadane’s algorithm.

Kadane’s algorithm is used to find the largest sum of the contiguous subarray.

So now Look at Kadane’s algorithm steps:-

  • Initialize:-

min_ele=max

min_end=max

  • Loop Statement:-

if min_ele>0

min_ele=a[i]

else

min_ele+=a[i]

So now we know the kadane’s algorithm’s opposite and implement that in finding the Smallest sum contiguous Subarray in Python.

But keep one thing in mind that these max size and min size is given by the sys library in Python.

So we need to import this.

import sys 
def smallest(arr,n):
    min_ele=sys.maxsize
    min_end=sys.maxsize 
    for i in range(n): 
        if min_ele>0: 
            min_ele=arr[i]
        else: 
            min_ele+=arr[i] 
        min_end=min(min_ele,min_end) 
    return min_end 
# Main Driver Program 
array=list(map(int,input().split())) 
n=len(array) 
print("The smallest contiguous sum is ",smallest(array,n))

Output:-

Leave a Reply

Your email address will not be published. Required fields are marked *