changeset 7:202259bcb331

DP: tighten code
author Lewin Bormann <lbo@spheniscida.de>
date Sun, 12 Mar 2023 22:48:09 +0100
parents 90bf264f80a5
children 60c7a574d536
files dynprog.cc
diffstat 1 files changed, 16 insertions(+), 43 deletions(-) [+]
line wrap: on
line diff
--- a/dynprog.cc	Sun Mar 12 21:49:53 2023 +0100
+++ b/dynprog.cc	Sun Mar 12 22:48:09 2023 +0100
@@ -87,29 +87,14 @@
     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.
+    size_t length_with_current = a.at(i) < a.at(prev) ? length : 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);
 
-        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;
+    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
@@ -118,28 +103,16 @@
     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;
-        }
+    T sum_with_this = a.at(i) < a.at(prev) ? sum : 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);
 
-        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;
+    }
 
-        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;
-    }
+    return result;
 }
 
 
@@ -189,7 +162,7 @@
     return 0;
 }
 
-int liss_main(void) {
+int 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
@@ -197,7 +170,7 @@
     return 0;
 }
 
-int main(void) {
+int msis_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