From 6d1af499c08ff609d533c9fce77d27e34bd7980c Mon Sep 17 00:00:00 2001
From: Paul Jungeblut <paul.jungeblut@gmail.com>
Date: Sat, 15 Oct 2016 23:56:51 +0200
Subject: Adding code for longest increasing subsequence.

---
 math/longestIncreasingSubsequence.cpp |  23 +++++++++++++++++++++++
 math/math.tex                         |   3 +++
 tcr.pdf                               | Bin 264965 -> 266240 bytes
 3 files changed, 26 insertions(+)
 create mode 100644 math/longestIncreasingSubsequence.cpp

diff --git a/math/longestIncreasingSubsequence.cpp b/math/longestIncreasingSubsequence.cpp
new file mode 100644
index 0000000..388e394
--- /dev/null
+++ b/math/longestIncreasingSubsequence.cpp
@@ -0,0 +1,23 @@
+vector<int> longestIncreasingSubsequence(vector<int> &seq) {
+  int n = seq.size(), lisLength = 0, lisEnd = 0;
+  vector<int> L(n), L_id(n), parents(n);
+  for (int i = 0; i < n; i++) {
+    int pos =
+      lower_bound(L.begin(), L.begin() + lisLength, seq[i]) - L.begin();
+    L[pos] = seq[i];
+    L_id[pos] = i;
+    parents[i] = pos ? L_id[pos - 1] : -1;
+    if (pos + 1 > lisLength) {
+      lisLength = pos + 1;
+      lisEnd = i;
+  }}
+  // Ab hier Rekonstruktion der Sequenz.
+  vector<int> result(lisLength);
+  int pos = lisLength - 1, x = lisEnd;
+  while (parents[x] >= 0) {
+    result[pos--] = x;
+    x = parents[x];
+  }
+  result[0] = x;
+  return result; // Liste mit Indizes einer LIS.
+}
diff --git a/math/math.tex b/math/math.tex
index a27c992..998fc2e 100644
--- a/math/math.tex
+++ b/math/math.tex
@@ -105,6 +105,9 @@ Multipliziert Polynome $A$ und $B$.
 \subsection{3D-Kugeln}
 \lstinputlisting{math/spheres.cpp}
 
+\subsection{Longest Increasing Subsequence}
+\lstinputlisting{math/longestIncreasingSubsequence.cpp}
+
 \subsection{Kombinatorik}
 
 \subsubsection{Berühmte Zahlen}
diff --git a/tcr.pdf b/tcr.pdf
index cb7ebbe..71acafc 100644
Binary files a/tcr.pdf and b/tcr.pdf differ
-- 
cgit v1.2.3