some lis improvements

jakobkogler · jakobkogler · commit bbd31229dfd9 · 2023-01-29T22:02:02.000+01:00
diff --git a/src/sequences/longest_increasing_subsequence.md b/src/sequences/longest_increasing_subsequence.md
@@ -27,26 +27,38 @@ First we will search only for the **length** of the longest increasing subsequen
 ### Finding the length
 
 To accomplish this task, we define an array $d[0 \dots n-1]$, where $d[i]$ is the length of the longest increasing subsequence that ends in the element at index $i$.
+
+!!! example
+
+    $$\begin{array}{ll}
+    a &= \{8, 3, 4, 6, 5, 2, 0, 7, 9, 1\} \\
+    d &= \{1, 1, 2, 2, 3, 1, 1, 4, 5, 2\}
+    \end{array}$$
+
+    The longest increasing subsequence that ends at index 4 is $\{3, 4, 5\}$ with a length of 3, the longest ending at index 8 is either $\{3, 4, 5, 7, 9\}$ or $\{3, 4, 6, 7, 9\}$, both having length 5, and the longest ending at index 9 is $\{0, 1\}$ having length 2.
+
 We will compute this array gradually: first $d[0]$, then $d[1]$, and so on.
 After this array is computed, the answer to the problem will be the maximum value in the array $d[]$.
 
 So let the current index be $i$.
 I.e. we want to compute the value $d[i]$ and all previous values $d[0], \dots, d[i-1]$ are already known.
 Then there are two options:
 
-- $d[i] = 1$: the required subsequence consists of only the element $a[i]$.
-- $d[i] > 1$: then in the required subsequence is another number before the number $a[i]$.
-  Let's focus on that number:
-  it can be any element $a[j]$ with $j = 0 \dots i-1$ and $a[j] < a[i]$.
-  In this fashion we can compute $d[i]$ using the following formula:
-  If we fixate the index $j$, then the longest increasing subsequence ending in the two elements $a[j]$ and $a[i]$ has the length $d[j] + 1$.
-  All of these values $d[j]$ are already known, so we can directly compute $d[i]$ with:
+-   $d[i] = 1$: the required subsequence consists only of the element $a[i]$.
+
+-   $d[i] > 1$: The subsequence will end it $a[i]$, and right before it will be some number $a[j]$ with $j < i$ and $a[j] < a[i]$.
+
+    It's easy to see, that the subsequence ending in $a[j]$ will itself be one of the longest increasing subsequences that ends in $a[j]$.
+    The number $a[i]$ just extends that longest increasing subsequence by one number.
+
+    Therefore, we can just iterate over all $j < i$ with $a[j] < a[i]$, and take the longest sequence that we get by appending $a[i]$ to the longest increasing subsequence ending in $a[j]$.
+    The longest increasing subsequence ending in $a[j]$ has length $d[j]$, extending it by one gives the length $d[j] + 1$.
   
-$$d[i] = \max_{\substack{j = 0 \dots i-1 \\\\ a[j] < a[i]}} \left(d[j] + 1\right)$$
+    $$d[i] = \max_{\substack{j < i \\\\ a[j] < a[i]}} \left(d[j] + 1\right)$$
 
 If we combine these two cases we get the final answer for $d[i]$:
 
-$$d[i] = \max\left(1, \max_{\substack{j = 0 \dots i-1 \\\\ a[j] < a[i]}} \left(d[j] + 1\right)\right)$$
+$$d[i] = \max\left(1, \max_{\substack{j < i \\\\ a[j] < a[i]}} \left(d[j] + 1\right)\right)$$
 
 ### Implementation
 
@@ -133,13 +145,47 @@ This method leads to a slightly longer code, but in return we save some memory.
 In order to obtain a faster solution for the problem, we construct a different dynamic programming solution that runs in $O(n^2)$, and then later improve it to $O(n \log n)$.
 
 We will use the dynamic programming array $d[0 \dots n]$.
-This time $d[i]$ will be the element at which a subsequence of length $i$ terminates.
-If there are multiple such sequences, then we take the one that ends in the smallest element.
+This time $d[l]$ doesn't corresponds to the element $a[i]$ or to an prefix of the array. 
+$d[l]$ will be the smallest element at which an increasing subsequence of length $l$ ends.
 
-Initially we assume $d[0] = -\infty$ and for all other elements $d[i] = \infty$.
+Initially we assume $d[0] = -\infty$ and for all other lengths $d[l] = \infty$.
 
 We will again gradually process the numbers, first $a[0]$, then $a[1]$, etc, and in each step maintain the array $d[]$ so that it is up to date.
 
+!!! example
+
+    Given the array $a = \{8, 3, 4, 6, 5, 2, 0, 7, 9, 1\}$, here are all their prefixes and their dynamic programming array.
+    Notice, that the values of the array don't always change at the end.
+
+    $$
+    \begin{array}{ll}
+    \text{prefix} = \{\} &\quad d = \{-\infty, \infty, \dots\}\\
+    \text{prefix} = \{8\} &\quad d = \{-\infty, 8, \infty, \dots\}\\
+    \text{prefix} = \{8, 3\} &\quad d = \{-\infty, 3, \infty, \dots\}\\
+    \text{prefix} = \{8, 3, 4\} &\quad d = \{-\infty, 3, 4, \infty, \dots\}\\
+    \text{prefix} = \{8, 3, 4, 6\} &\quad d = \{-\infty, 3, 4, 6, \infty, \dots\}\\
+    \text{prefix} = \{8, 3, 4, 6, 5\} &\quad d = \{-\infty, 3, 4, 5, \infty, \dots\}\\
+    \text{prefix} = \{8, 3, 4, 6, 5, 2\} &\quad d = \{-\infty, 2, 4, 5, \infty, \dots \}\\
+    \text{prefix} = \{8, 3, 4, 6, 5, 2, 0\} &\quad d = \{-\infty, 0, 4, 5, \infty, \dots \}\\
+    \text{prefix} = \{8, 3, 4, 6, 5, 2, 0, 7\} &\quad d = \{-\infty, 0, 4, 5, 7, \infty, \dots \}\\
+    \text{prefix} = \{8, 3, 4, 6, 5, 2, 0, 7, 9\} &\quad d = \{-\infty, 0, 4, 5, 7, 9, \infty, \dots \}\\
+    \text{prefix} = \{8, 3, 4, 6, 5, 2, 0, 7, 9, 1\} &\quad d = \{-\infty, 0, 1, 5, 7, 9, \infty, \dots \}\\
+    \end{array}
+    $$
+
+When we process $a[i]$, we can ask ourselves.
+What have the conditions to be, that we write the current number $a[i]$ into the $d[0 \dots n]$ array?
+
+We set $d[l] = a[i]$, if there is a longest increasing sequence of length $l$ that ends in $a[i]$, and there is no longest increasing sequence of length $l$ that ends in a smaller number.
+Similar to the previous approach, if we remove the number $a[i]$ from the longest increasing sequence of length $l$, we get another longest increasing sequence of length $l -1$.
+So we want to extend a longest increasing sequence of length $l - 1$ by the number $a[i]$, and obviously the longest increasing sequence of length $l - 1$ that ends with the smallest element will work the best, in other words the sequence of length $l-1$ that ends in element $d[l-1]$.
+
+There is a longest increasing sequence of length $l - 1$ that we can extend with the number $a[i]$, exactly if $d[l-1] < a[i]$.
+So we can just iterate over each length $l$, and check if we can extend a longest increasing sequence of length $l - 1$ by checking the criteria.
+
+Additionally we also need to check, if we maybe have already found a longest increasing sequence of length $l$ with a smaller number at the end.
+So we only update if $a[i] < d[l]$.
+
 After processing all the elements of $a[]$ the length of the desired subsequence is the largest $l$ with $d[l] < \infty$.
 
 ```{.cpp file=lis_method2_n2}
@@ -150,32 +196,40 @@ int lis(vector<int> const& a) {
     d[0] = -INF;
 
     for (int i = 0; i < n; i++) {
-        for (int j = 1; j <= n; j++) {
-            if (d[j-1] < a[i] && a[i] < d[j])
-                d[j] = a[i];
+        for (int l = 1; l <= n; l++) {
+            if (d[l-1] < a[i] && a[i] < d[l])
+                d[l] = a[i];
         }
     }
 
     int ans = 0;
-    for (int i = 0; i <= n; i++) {
-        if (d[i] < INF)
-            ans = i;
+    for (int l = 0; l <= n; l++) {
+        if (d[l] < INF)
+            ans = l;
     }
     return ans;
 }
 ```
 
 We now make two important observations.
 
-The array $d$ will always be sorted: 
-$d[i-1] \le d[i]$ for all $i = 1 \dots n$.
-And also the element $a[i]$ will only update at most one value $d[j]$.
+1.  The array $d$ will always be sorted: 
+    $d[l-1] < d[l]$ for all $i = 1 \dots n$.
 
-Thus we can find this element in the array $d[]$ using binary search in $O(\log n)$.
-In fact we are simply looking in the array $d[]$ for the first number that is strictly greater than $a[i]$, and we try to update this element in the same way as the above implementation.
+    This is trivial, as you can just remove the last element from the increasing subsequence of length $l$, and you get a increasing subsequence of length $l-1$ with a smalller ending number.
+
+2.  The element $a[i]$ will only update at most one value $d[l]$.
+
+    This follows immediately from the above implementation.
+    There can only be one place in the array with $d[l-1] < a[i] < d[l]$.
+
+Thus we can find this element in the array $d[]$ using [binary search](../num_methods/binary_search.md) in $O(\log n)$.
+In fact we can simply look in the array $d[]$ for the first number that is strictly greater than $a[i]$, and we try to update this element in the same way as the above implementation.
 
 ### Implementation
 
+This gives us the improved $O(n \log n)$ implementation:
+
 ```{.cpp file=lis_method2_nlogn}
 int lis(vector<int> const& a) {
     int n = a.size();
@@ -184,15 +238,15 @@ int lis(vector<int> const& a) {
     d[0] = -INF;
 
     for (int i = 0; i < n; i++) {
-        int j = upper_bound(d.begin(), d.end(), a[i]) - d.begin();
-        if (d[j-1] < a[i] && a[i] < d[j])
-            d[j] = a[i];
+        int l = upper_bound(d.begin(), d.end(), a[i]) - d.begin();
+        if (d[l-1] < a[i] && a[i] < d[l])
+            d[l] = a[i];
     }
 
     int ans = 0;
-    for (int i = 0; i <= n; i++) {
-        if (d[i] < INF)
-            ans = i;
+    for (int l = 0; l <= n; l++) {
+        if (d[l] < INF)
+            ans = l;
     }
     return ans;
 }
