--- a/dynprog.cc	Sun Mar 12 16:11:39 2023 +0100
+++ b/dynprog.cc	Sun Mar 12 21:49:53 2023 +0100
@@ -10,9 +10,6 @@
 #include <unordered_map>
 #include <vector>
 
-#include <fmt/core.h>
-#include <fmt/ranges.h>
-
 using namespace std;
 
 using MemoKey = tuple<size_t, size_t, size_t>;
@@ -83,7 +80,106 @@
     fmt::print("{}\n", result);
 }
 
-int main(void) {
+template <typename T>
+size_t longest_increasing_subsequence(const vector<T> &a, size_t i, size_t prev,
+                                      size_t length, size_t &longest,
+                                      vector<size_t> &seqixs) {
+    longest = max(length, longest);
+    if (i >= a.size()) return length;
+
+    // Need to restart series?
+    if (a.at(i) < a.at(prev)) {
+        size_t length_with_new = longest_increasing_subsequence(a, i+1, i, 1, longest, seqixs);
+        size_t length_with_skip = longest_increasing_subsequence(a, i+1, prev, length, longest, seqixs);
+        size_t result = max(length_with_new, length_with_skip);
+
+        // If current element started the sequence: update seqixs.
+        if (result == length_with_new && result == longest) {
+            seqixs.at(0) = i;
+        }
+        // Else: current element not included in sequence.
+
+        return result;
+    } else {  // We can include or exclude current element i.
+        size_t length_with_current = longest_increasing_subsequence(a, i+1, i, length+1, longest, seqixs);
+        size_t length_without_current = longest_increasing_subsequence(a, i+1, prev, length, longest, seqixs);
+        size_t result = max(length_with_current, length_without_current);
+
+        if (result == length_with_current && result == longest) {
+            seqixs.at(length) = i;
+        }
+        return result;
+    }
+}
+
+// Bug: if first element is 0 or negative, may repeat last index in seqixs
+template<typename T>
+T max_sum_incr_subseq(const vector<T>& a, size_t i, size_t prev, size_t length, T sum, T& highest_sum, vector<size_t>& seqixs) {
+    highest_sum = max(sum, highest_sum);
+    if (i >= a.size()) return sum;
+
+    if (a.at(i) < a.at(prev)) {
+        T sum_with_new = max_sum_incr_subseq(a, i+1, i, 1, a.at(i), highest_sum, seqixs);
+        T sum_with_skip = max_sum_incr_subseq(a, i+1, prev, length, sum, highest_sum, seqixs);
+        T result = max(sum_with_new, sum_with_skip);
+
+        if (result == sum_with_new && sum_with_new == highest_sum) {
+            seqixs.at(0) = i;
+        }
+
+        return result;
+    } else {
+        T sum_with_this = max_sum_incr_subseq(a, i+1, i, length+1, sum + a.at(i), highest_sum, seqixs);
+        T sum_without_this = max_sum_incr_subseq(a, i+1, prev, length, sum, highest_sum, seqixs);
+        T result = max(sum_with_this, sum_without_this);
+
+        if (result == sum_with_this && sum_with_this > sum_without_this && sum_with_this == highest_sum) {
+            if (i == 7 && length == 3) fmt::print("{} {} {} {} {} / {} - {}\n", i, prev, length, sum, highest_sum, sum_with_this, sum_without_this);
+            seqixs.at(length) = i;
+        }
+
+        return result;
+    }
+}
+
+
+template<typename T, template<typename> typename C>
+void evaluate_liss(const C<T>& v) requires ranges::range<C<T>> {
+    vector<T> a(v.begin(), v.end());
+    size_t longest = 0;
+    vector<size_t> seqixs(a.size());
+    size_t result = timeit_f(function([&a,&longest,&seqixs]() -> size_t { return longest_increasing_subsequence(a, 0, 0, 0, longest, seqixs); }), "longest incr. subsequence");
+
+    fmt::print("Longest incr. subsequence has length {}/{} and has indices: {}\n", longest, result, seqixs);
+    
+    vector<T> seq(longest);
+    for (int i = 0; i < seq.size(); i++)
+        seq.at(i) = a.at(seqixs.at(i));
+    fmt::print("Longest incr. subsequence is: {}\n", seq);
+}
+
+template<typename T, template<typename> typename C>
+void evaluate_msis(const C<T>& v) requires ranges::range<C<T>> {
+    vector<T> a(v.begin(), v.end());
+    T highest = 0;
+    vector<size_t> seqixs(a.size());
+    size_t result =
+        timeit_f(function([&a, &highest, &seqixs]() -> size_t {
+                   return max_sum_incr_subseq(a, 0, 0, 0, static_cast<T>(0), highest, seqixs);
+                 }),
+                 "max sum incr. subsequence");
+
+    fmt::print("Max incr sum subseq subsequence has sum {}/{} and has indices: {}\n", highest, result, seqixs);
+    
+    vector<T> seq(seqixs.size());
+    for (int i = 0; i < seq.size(); i++) {
+        if (i > 0 && seqixs.at(i) == 0) break;
+        seq.at(i) = a.at(seqixs.at(i));
+    }
+    fmt::print("Max sum incr. subsequence is: {}\n", seq);
+}
+
+int lcss_main(void) {
 
     vector<int> a{1,6,2,-1,3,55,2,4,23,5,6,7,8,9,10};
     vector<int> b{-3, 1, 5, 7, 2, 4, -1, 3, 6, 7, 9, 11, 10};
@@ -92,3 +188,19 @@
     evaluate_lcss(views::single(11), views::single(11));
     return 0;
 }
+
+int liss_main(void) {
+    vector<int> a{0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11};
+    // Expect: 0,2,6,9,13 or ,11
+    // or 0,4,6,9,13
+    evaluate_liss(a);
+    return 0;
+}
+
+int main(void) {
+    vector<int> a{-1, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11};
+    // Expect: 0,2,6,9,13 or ,11
+    // or 0,4,6,9,13
+    evaluate_msis(a);
+    return 0;
+}

--- a/lib/exec.cc	Sun Mar 12 16:11:39 2023 +0100
+++ b/lib/exec.cc	Sun Mar 12 21:49:53 2023 +0100
@@ -16,7 +16,7 @@
     decltype(d)::rep count = d.count();
     decltype(d)::period p;
 
-    cout << name << " :: " << static_cast<double>(p.num)/p.den * count << endl;
+    fmt::print("{} :: {} s\n", name, static_cast<double>(p.num)/p.den * count); 
 }
 
 void benchmarkit(function<void()> f, string name, function<void()> setup) {
@@ -27,7 +27,7 @@
     while (true) {
         setup();
      
-        cout << "Running " << name << " for " << n << " iterations.\n";
+        fmt::print("Running {} for {} iterations\n", name, n);
 
         auto begin = high_resolution_clock::now();
 
@@ -40,7 +40,7 @@
         if (seconds < min_duration) {
             n *= 2;
         } else {
-            cout << n << " iterations took " << seconds << " seconds (" << seconds/n << " s/iter)\n";
+            fmt::print("{} iterations took {} seconds ({} s/iter)\n", n, seconds, seconds/n);
             break;
         }
     }

--- a/lib/exec.h	Sun Mar 12 16:11:39 2023 +0100
+++ b/lib/exec.h	Sun Mar 12 21:49:53 2023 +0100
@@ -1,8 +1,10 @@
+
+#include <fmt/core.h>
+#include <fmt/ranges.h>
 
 
 #include <chrono>
 #include <functional>
-#include <iostream>
 #include <string>
 void timeit(std::function<void()> f, std::string name = std::string());
 
@@ -22,6 +24,6 @@
     decltype(d)::rep count = d.count();
     decltype(d)::period p;
 
-    std::cout << name << " :: " << static_cast<double>(p.num)/p.den * count << std::endl;
+    fmt::print("{} :: {} s\n", name, static_cast<double>(p.num)/p.den * count); 
     return result;
 }