CODEWITHSUNDEEP
c++algorithmdynamic-programming
Gabriel Henrique
Gabriel Henrique

Reputation: 48

Length of the longest decreasing subsequence built by appending elements to the end and the front using dynamic programming

The restrictions are that the elements can be appended to the front if they are greater than the element at the front and to the back if they are smaller than the back. It can also ignore elements (and there comes the difficulty).

Example:

Input: {6, 7, 3, 5, 4}

The longest sequence to that input is:

If we appended 3, the sequence would be smaller {7, 6, 3} because then we wouldn't be able to append 4.

I tried to adapt a LIS algorithm to solve it, but the results are totally wrong.

int adapted_LIS(int input[], int n)
{
    int score[n] = {};
    score[0] = 1;
    for (int i = 1; i < n; i++)
    {
        score[i] = 1;
        int front = input[i];
        int back = input[i];
        for (int j = 0; j < i; j++)
        {
            if (input[j] > front)
            {
                front = input[j];
                score[i] = std::max(score[i], score[j] + 1);
            }
            else if (input[j] < back)
            {
                back = input[j];
                score[i] = std::max(score[i], score[j] + 1);
            }
        }
    }
    return *std::max_element(score, score + n);
}

How can I solve it using Dynamic Programming?

Upvotes: 2

Views: 413

Answers (1)

David Eisenstat
David Eisenstat

Reputation: 65458

The optimal substructure that we need for dynamic programming is that, given two sequences with the same front and back, it’s obviously better to extend the longer one (or the same, if the sequences have the same length). Here’s some C++. It’s inefficient for clarity and so that it can’t be fed directly to an online judge, but there’s a straightforward path to O(n³). With a little data structural cleverness, O(n² log n).

#include <algorithm>
#include <iostream>
#include <map>
#include <utility>
#include <vector>

std::vector<int> PushFront(int x, std::vector<int> subsequence) {
  subsequence.insert(subsequence.begin(), x);
  return subsequence;
}

std::vector<int> PushBack(std::vector<int> subsequence, int x) {
  subsequence.push_back(x);
  return subsequence;
}

void Consider(std::map<std::pair<int, int>, std::vector<int>> &table,
              std::vector<int> subsequence) {
  std::vector<int> &entry = table[{subsequence.front(), subsequence.back()}];
  if (subsequence.size() > entry.size()) {
    entry = std::move(subsequence);
  }
}

std::vector<int> TwoSidedDecreasingSubsequence(const std::vector<int> &input) {
  if (input.empty()) {
    return {};
  }
  // Maps {front, back} to the longest known subsequence.
  std::map<std::pair<int, int>, std::vector<int>> table;
  for (int x : input) {
    auto table_copy = table;
    for (const auto &[front_back, subsequence] : table_copy) {
      auto [front, back] = front_back;
      if (x > front) {
        Consider(table, PushFront(x, subsequence));
      }
      if (back > x) {
        Consider(table, PushBack(subsequence, x));
      }
    }
    Consider(table, {x});
  }
  return std::max_element(
             table.begin(), table.end(),
             [&](const std::pair<std::pair<int, int>, std::vector<int>> &a,
                 const std::pair<std::pair<int, int>, std::vector<int>> &b) {
               return a.second.size() < b.second.size();
             })
      ->second;
}

int main() {
  for (int x : TwoSidedDecreasingSubsequence({6, 7, 3, 5, 4})) {
    std::cout << ' ' << x;
  }
  std::cout << '\n';
}

Upvotes: 3

Related Questions