Merge pull request souravjain540#148 from dinesh9-ai/main

souravjain540 · web-flow · commit a0cbb1accf74 · 2023-08-15T19:57:21.000+05:30
added kadanes algorithm
diff --git a/kadanes_algorithm.py b/kadanes_algorithm.py
@@ -0,0 +1,18 @@
+"""
+This algorithm is used to find the largest sum in the given array in O(n) Time complexity
+"""
+
+arr=[-1,0,3,4,2,6,-10,5,-9]
+
+max_sum=0
+curr_sum=0
+
+for i in arr:
+    curr_sum += i
+    max_sum=max(max_sum,curr_sum)
+    
+    if curr_sum<0:
+        curr_sum=0
+
+
+print(max_sum)
