Mercurial > lbo > hg > ccplay
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