Repository: keon/algorithms
Pull request #588 (2019-11-06 15:14:09)

Add dp longest increasing optimized
(Put an `X` inside the `[ ]` to denote check mark `[X]`.)


- [ ] **If creating a new file :**
  - [ ] added links to it in the README files ?
  - [ ] included tests with it ?
  - [ ] added description (overview of algorithm, time and space complexity, and possible edge case) in docstrings ?

- [X] **if done some changes :**
  - [X] wrote short description in the PR explaining what the changes do ?
  - [ ] Fixes #[issue number] if related to any issue

- [ ] **other**


keon: could you add the unitttests?

Patch:
diff --git a/README.md b/README.md
index a127f59..f288ee3 100644
--- a/README.md
+++ b/README.md
@@ -341,6 +341,7 @@ If you want to uninstall algorithms, it is as simple as:
         - [red_black_tree](algorithms/tree/red_black_tree/red_black_tree.py)
     - [segment_tree](algorithms/tree/segment_tree)
         - [segment_tree](algorithms/tree/segment_tree/segment_tree.py)
+        - [iterative_segment_tree](algorithms/tree/segment_tree/iterative_segment_tree.py)
     - [traversal](algorithms/tree/traversal)
         - [inorder](algorithms/tree/traversal/inorder.py)
         - [level_order](algorithms/tree/traversal/level_order.py)
diff --git a/algorithms/dp/longest_increasing.py b/algorithms/dp/longest_increasing.py
index 7197137..6cae572 100644
--- a/algorithms/dp/longest_increasing.py
+++ b/algorithms/dp/longest_increasing.py
@@ -7,14 +7,23 @@ Input: [10,9,2,5,3,7,101,18]
 Output: 4 
 Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.
 
-The time complexity is O(n^2).
+Time complexity:
+First algorithm is O(n^2).
+Second algorithm is O(nlogx) where x is the max element in the list
+Third algorithm is O(nlogn)
+
+Space complexity:
+First algorithm is O(n)
+Second algorithm is O(x) where x is the max element in the list
+Third algorithm is O(n)
 """
 
 def longest_increasing_subsequence(sequence):
     """
     Dynamic Programming Algorithm for
     counting the length of longest increasing subsequence
-    type sequence: List[int]
+    type sequence: list[int]
+    rtype: int
     """
     length = len(sequence)
     counts = [1 for _ in range(length)]
@@ -24,3 +33,79 @@ def longest_increasing_subsequence(sequence):
                 counts[i] = max(counts[i], counts[j] + 1)
                 print(counts)
     return max(counts)
+
+def longest_increasing_subsequence_optimized(sequence):
+    """
+    Optimized dynamic programming algorithm for
+    couting the length of the longest increasing subsequence
+    using segment tree data structure to achieve better complexity
+    if max element is larger than 10^5 then use 
+    longest_increasing_subsequence_optimied2() instead
+    type sequence: list[int]
+    rtype: int
+    """
+    mx = max(sequence)
+    tree = [0] * (mx<<2)
+
+    def update(p, l, r, i, v):
+        if l == r:
+            tree[p] = v
+            return
+        mid = (l+r)>>1
+        if i <= mid:
+            update(p<<1, l, mid, i, v)
+        else:
+            update((p<<1)|1, mid+1, r, i, v)
+        tree[p] = max(tree[p<<1], tree[(p<<1)|1])
+
+    def get_max(p, l, r, s, e):
+        if l > e or r < s:
+            return 0
+        if l >= s and r <= e:
+            return tree[p]
+        mid = (l+r)>>1
+        return max(get_max(p<<1, l, mid, s, e), get_max((p<<1)|1, mid+1, r, s, e))
+    ans = 0
+    for x in sequence:
+       cur = get_max(1, 0, mx, 0, x-1)+1
+       ans = max(ans, cur)
+       update(1, 0, mx, x, cur)
+    return ans
+
+def longest_increasing_subsequence_optimized2(sequence):
+    """
+    Optimized dynamic programming algorithm for
+    counting the length of the longest increasing subsequence
+    using segment tree data structure to achieve better complexity
+    type sequence: list[int]
+    rtype: int
+    """
+    n = len(sequence)
+    tree = [0] * (n<<2)
+    sorted_seq = sorted((x, -i) for i, x in enumerate(sequence))
+    def update(p, l, r, i, v):
+        if l ==r:
+            tree[p] = v
+            return
+        mid = (l+r)>>1
+        if i <= mid:
+            update(p<<1, l, mid, i, v)
+        else:
+            update((p<<1)|1, mid+1, r, i, v)
+        tree[p] = max(tree[p<<1], tree[(p<<1)|1])
+
+    def get_max(p, l, r, s, e):
+        if l > e or r < s:
+            return 0
+        if l >= s and r <= e:
+            return tree[p]
+        mid = (l+r)>>1
+        return max(get_max(p<<1, l, mid, s, e), get_max((p<<1)|1, mid+1, r, s, e))
+    ans = 0
+    for x, j in sorted_seq:
+        i = -j
+        cur = get_max(1, 0, n-1, 0, i-1)+1
+        ans = max(ans, cur)
+        update(1, 0, n-1, i, cur)
+    return ans 
+
diff --git a/algorithms/tree/segment_tree/iterative_segment_tree.py b/algorithms/tree/segment_tree/iterative_segment_tree.py
new file mode 100644
index 0000000..84018ed
--- /dev/null
+++ b/algorithms/tree/segment_tree/iterative_segment_tree.py
@@ -0,0 +1,53 @@
+"""
+SegmentTree creates a segment tree with a given array and a "commutative" function,
+this non-recursive version uses less memory than the recursive version and include:
+1. range queries in log(N) time
+2. update an element in log(N) time
+the function should be commutative and takes 2 values and returns the same type value
+
+Examples -
+mytree = SegmentTree([2, 4, 5, 3, 4],max)
+print(mytree.query(2, 4))
+mytree.update(3, 6)
+print(mytree.query(0, 3)) ...
+
+mytree = SegmentTree([4, 5, 2, 3, 4, 43, 3], lambda a, b: a + b)
+print(mytree.query(0, 6))
+mytree.update(2, -10)
+print(mytree.query(0, 6)) ...
+
+mytree = SegmentTree([(1, 2), (4, 6), (4, 5)], lambda a, b: (a[0] + b[0], a[1] + b[1]))
+print(mytree.query(0, 2))
+mytree.update(2, (-1, 2))
+print(mytree.query(0, 2)) ...
+"""
+
+
+class SegmentTree:
+    def __init__(self, arr, function):
+        self.tree = [None for _ in range(len(arr))] + arr
+        self.size = len(arr)
+        self.fn = function
+        self.build_tree()
+
+    def build_tree(self):
+        for i in range(self.size - 1, 0, -1):
+            self.tree[i] = self.fn(self.tree[i * 2], self.tree[i * 2 + 1])
+
+    def update(self, p, v):
+        p += self.size
+        self.tree[p] = v
+        while p > 1:
+            p = p // 2
+            self.tree[p] = self.fn(self.tree[p * 2], self.tree[p * 2 + 1])
+
+    def query(self, l, r):
+        l, r = l + self.size, r + self.size
+        res = None
+        while l <= r:
+            if l % 2 == 1:
+                res = self.tree[l] if res is None else self.fn(res, self.tree[l])
+            if r % 2 == 0:
+                res = self.tree[r] if res is None else self.fn(res, self.tree[r])
+            l, r = (l + 1) // 2, (r - 1) // 2
+        return res


Test patch:
diff --git a/tests/test_dp.py b/tests/test_dp.py
index cd1dde2..f02921a 100644
--- a/tests/test_dp.py
+++ b/tests/test_dp.py
@@ -11,6 +11,8 @@ from algorithms.dp import (
     Job, schedule,
     Item, get_maximum_value,
     longest_increasing_subsequence,
+    longest_increasing_subsequence_optimized,
+    longest_increasing_subsequence_optimized2,
     int_divide
 )
 
@@ -135,6 +137,18 @@ class TestLongestIncreasingSubsequence(unittest.TestCase):
         self.assertEqual(5, longest_increasing_subsequence(sequence))
 
 
+class TestLongestIncreasingSubsequenceOptimized(unittest.TestCase):
+    def test_longest_increasing_subsequence_optimized(self):
+        sequence = [1, 101, 10, 2, 3, 100, 4, 6, 2]
+        self.assertEqual(5, longest_increasing_subsequence(sequence))
+
+
+class TestLongestIncreasingSubsequenceOptimized2(unittest.TestCase):
+    def test_longest_increasing_subsequence_optimized2(self):
+        sequence = [1, 101, 10, 2, 3, 100, 4, 6, 2]
+        self.assertEqual(5, longest_increasing_subsequence(sequence))
+
+
 class TestIntDivide(unittest.TestCase):
     def test_int_divide(self):
         self.assertEqual(5, int_divide(4))
diff --git a/tests/test_iterative_segment_tree.py b/tests/test_iterative_segment_tree.py
new file mode 100644
index 0000000..b9a611a
--- /dev/null
+++ b/tests/test_iterative_segment_tree.py
@@ -0,0 +1,91 @@
+from algorithms.tree.segment_tree.iterative_segment_tree import SegmentTree
+from functools import reduce
+
+import unittest
+
+
+def gcd(a, b):
+    if b == 0:
+        return a
+    return gcd(b, a % b)
+
+
+class TestSegmentTree(unittest.TestCase):
+    """
+    Test for the Iterative Segment Tree data structure
+    """
+
+    def test_segment_tree_creation(self):
+        arr = [2, 4, 3, 6, 8, 9, 3]
+        max_segment_tree = SegmentTree(arr, max)
+        min_segment_tree = SegmentTree(arr, min)
+        sum_segment_tree = SegmentTree(arr, lambda a, b: a + b)
+        gcd_segment_tree = SegmentTree(arr, gcd)
+        self.assertEqual(max_segment_tree.tree, [None, 9, 8, 9, 4, 8, 9, 2, 4, 3, 6, 8, 9, 3])
+        self.assertEqual(min_segment_tree.tree, [None, 2, 3, 2, 3, 6, 3, 2, 4, 3, 6, 8, 9, 3])
+        self.assertEqual(sum_segment_tree.tree, [None, 35, 21, 14, 7, 14, 12, 2, 4, 3, 6, 8, 9, 3])
+        self.assertEqual(gcd_segment_tree.tree, [None, 1, 1, 1, 1, 2, 3, 2, 4, 3, 6, 8, 9, 3])
+
+    def test_max_segment_tree(self):
+        arr = [-1, 1, 10, 2, 9, -3, 8, 4, 7, 5, 6, 0]
+        self.__test_all_segments(arr, max)
+
+    def test_min_segment_tree(self):
+        arr = [1, 10, -2, 9, -3, 8, 4, -7, 5, 6, 11, -12]
+        self.__test_all_segments(arr, min)
+
+    def test_sum_segment_tree(self):
+        arr = [1, 10, 2, 9, 3, 8, 4, 7, 5, 6, -11, -12]
+        self.__test_all_segments(arr, lambda a, b: a + b)
+
+    def test_gcd_segment_tree(self):
+        arr = [1, 10, 2, 9, 3, 8, 4, 7, 5, 6, 11, 12, 14]
+        self.__test_all_segments(arr, gcd)
+
+    def test_max_segment_tree_with_updates(self):
+        arr = [-1, 1, 10, 2, 9, -3, 8, 4, 7, 5, 6, 0]
+        updates = {0: 1, 1: 2, 2: 3, 3: 4, 4: 5, 5: 6, 6: 7, 7: 8, 8: 9, 9: 10, 10: 11, 11: 12}
+        self.__test_all_segments_with_updates(arr, max, updates)
+
+    def test_min_segment_tree_with_updates(self):
+        arr = [1, 10, -2, 9, -3, 8, 4, -7, 5, 6, 11, -12]
+        updates = {0: 7, 1: 2, 2: 6, 3: -14, 4: 5, 5: 4, 6: 7, 7: -10, 8: 9, 9: 10, 10: 12, 11: 1}
+        self.__test_all_segments_with_updates(arr, min, updates)
+
+    def test_sum_segment_tree_with_updates(self):
+        arr = [1, 10, 2, 9, 3, 8, 4, 7, 5, 6, -11, -12]
+        updates = {0: 12, 1: 11, 2: 10, 3: 9, 4: 8, 5: 7, 6: 6, 7: 5, 8: 4, 9: 3, 10: 2, 11: 1}
+        self.__test_all_segments_with_updates(arr, lambda a, b: a + b, updates)
+
+    def test_gcd_segment_tree_with_updates(self):
+        arr = [1, 10, 2, 9, 3, 8, 4, 7, 5, 6, 11, 12, 14]
+        updates = {0: 4, 1: 2, 2: 3, 3: 9, 4: 21, 5: 7, 6: 4, 7: 4, 8: 2, 9: 5, 10: 17, 11: 12, 12: 3}
+        self.__test_all_segments_with_updates(arr, gcd, updates)
+
+    def __test_all_segments(self, arr, fnc):
+        """
+        Test all possible segments in the tree
+        :param arr: array to test
+        :param fnc: function of the segment tree
+        """
+        segment_tree = SegmentTree(arr, fnc)
+        self.__test_segments_helper(segment_tree, fnc, arr)
+
+    def __test_all_segments_with_updates(self, arr, fnc, upd):
+        """
+        Test all possible segments in the tree with updates
+        :param arr: array to test
+        :param fnc: function of the segment tree
+        :param upd: updates to test
+        """
+        segment_tree = SegmentTree(arr, fnc)
+        for index, value in upd.items():
+            arr[index] = value
+            segment_tree.update(index, value)
+            self.__test_segments_helper(segment_tree, fnc, arr)
+
+    def __test_segments_helper(self, seg_tree, fnc, arr):
+        for i in range(0, len(arr)):
+            for j in range(i, len(arr)):
+                range_value = reduce(fnc, arr[i:j + 1])
+                self.assertEqual(seg_tree.query(i, j), range_value)