Repository: keon/algorithms (python)

Issue:
Small typo in algorithms/search/jump_search.py
Should be target rather than taget.

Pull request:
Fix simple typo: taget -> target
- [x] **if done some changes :**
  - [x] wrote short description in the PR explaining what the changes do ?

Resolves a small typo in a comment in algorithms/search/jump_search.py

  - [x] Fixes #590

Patch:
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/search/jump_search.py b/algorithms/search/jump_search.py
index 66f726a..da8d8c3 100644
--- a/algorithms/search/jump_search.py
+++ b/algorithms/search/jump_search.py
@@ -16,7 +16,7 @@ def jump_search(arr,target):
     block_prev = 0
     block= block_size
 
-    # return -1 means that array doesn't contain taget value
+    # return -1 means that array doesn't contain target value
     # find block that contains target value
     
     if arr[n - 1] < target:


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))