Added Kadane algorithm for max_contiguous_subsequence_sum problem with requested changes. (keon#861)

iabhishek15 · web-flow · commit 6440664a3182 · 2022-03-08T18:31:42.000+05:30
* initial commit * initial commit! * Added Kadane's Algorithm for max_contiguous_subsequence_sum problem! * Update README.md * Update max_contiguous_subsequence_sum.py * Update max_contiguous_subsequence_sum.py * fix keon#854
diff --git a/README.md b/README.md
@@ -71,6 +71,8 @@ If you want to uninstall algorithms, it is as simple as:
     - [two_sum](algorithms/arrays/two_sum.py)
     - [move_zeros](algorithms/arrays/move_zeros.py)
     - [n_sum](algorithms/arrays/n_sum.py)
+- [greedy](algorithms/greedy/)
+    - [max_contiguous_subsequence_sum](algorithms/greedy/max_contiguous_subsequence_sum.py)
 - [automata](algorithms/automata)
     - [DFA](algorithms/automata/dfa.py)
 - [backtrack](algorithms/backtrack)
diff --git a/algorithms/greedy/__init__.py b/algorithms/greedy/__init__.py
@@ -0,0 +1 @@
+from .max_contiguous_subsequence_sum import *
diff --git a/algorithms/greedy/max_contiguous_subsequence_sum.py b/algorithms/greedy/max_contiguous_subsequence_sum.py
@@ -0,0 +1,42 @@
+'''
+Algorithm used => Kadane's Algorithm
+
+kadane's algorithm is used for finding the maximum sum of contiguous subsequence in a sequence.
+It is considered a greedy/dp algorithm but I think they more greedy than dp
+here are some of the examples to understand the use case more clearly
+Example1 => [-2, 3, 8, -1, 4]
+result =>  {3, 8, -1, 4} => 14
+Example2 => [-1, 1, 0]
+result => {1} => 1
+Example3 => [-1, -3, -4]
+result => -1
+Example1 => [-2, 3, 8, -12, 8, 4]
+result =>  {8, 4} => 12
+Basic Algorithm Idea
+    If the sum of the current contiguous subsequence after adding the value at the current position is less than the value
+    at the current position then we know that it will be better if we start the current contiguous subsequence from this position.
+    Else we add the value at the current position to the current contiguous subsequence.
+Note
+    In the implementation, the contiguous subsequence has at least one element.
+    If it can have 0 elements then the result will be max(max_till_now, 0)
+'''
+
+
+def max_contiguous_subsequence_sum(arr) -> int:
+    arr_size = len(arr)
+
+    if arr_size == 0:
+        return 0
+
+    max_till_now = arr[0]
+    curr_sub_sum = 0
+
+    for i in range(0, arr_size):
+        if curr_sub_sum + arr[i] < arr[i]:
+            curr_sub_sum = arr[i]
+        else:
+            curr_sub_sum += arr[i]
+
+        max_till_now = max(max_till_now, curr_sub_sum)
+
+    return max_till_now
diff --git a/tests/test_greedy.py b/tests/test_greedy.py
@@ -0,0 +1,21 @@
+from algorithms.greedy import (
+    max_contiguous_subsequence_sum,
+)
+
+import unittest
+
+class TestMaxContiguousSubsequenceSum(unittest.TestCase):
+    def test_max_contiguous_subsequence_sum(self):
+        arr1 = [-2, 3, 8, -1, 4]
+        arr2 = [-1, 1, 0]
+        arr3 = [-1, -3, -4]
+        arr4 = [-2, 3, 8, -12, 8, 4]
+
+        self.assertEqual(max_contiguous_subsequence_sum(arr1), 14)
+        self.assertEqual(max_contiguous_subsequence_sum(arr2), 1)
+        self.assertEqual(max_contiguous_subsequence_sum(arr3), -1)
+        self.assertEqual(max_contiguous_subsequence_sum(arr4), 12)
+
+if __name__ == '__main__':
+
+    unittest.main()

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1 @@`
	`1`	`+from .max_contiguous_subsequence_sum import *`