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