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:

• Start with {6}.

• Append 7 to the front because it is greater than 6. {7, 6}

• Ignore 3.

• Append 5 to the back because it is smaller. {7, 6, 5}

• Append 4 to the back because it is smaller. {7, 6, 5, 4}

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?

CodePudding user response：

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 (inefficient for clarity and so that it can’t be fed directly to an online judge):

#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';
}

CodePudding user response：

You're trying to use the Longest Increasing Subsequence (LIS) algorithm to solve this problem, but that won't work because the rules for constructing a valid sequence in this problem are different from the rules for constructing a longest increasing subsequence.

To solve this problem using dynamic programming, you'll need to come up with a new approach that takes into account the specific rules for appending elements to the front or back of the sequence.

One way to do this is to create two separate dynamic programming arrays, one to keep track of the longest sequence ending at the front of the array, and another to keep track of the longest sequence ending at the back of the array. Then, you can iterate over the input array and update these two arrays based on the rules for appending elements to the front or back of the sequence.

Here's a rough outline of my proposed solution: (This should serve as an explanation to the code snippet below)

1. Initialize two dynamic programming arrays, front and back, both of size n. Set all elements of these arrays to 1.

2. Iterate over the input array from left to right. At each step i, do the following:

   1. If the element at index i is greater than the element at the front of the sequence (i.e., the element at index front[i-1] in the input array), append this element to the front of the sequence by setting front[i] to front[i-1] 1.
   2. If the element at index i is smaller than the element at the back of the sequence (i.e., the element at index back[i-1] in the input array), append this element to the back of the sequence by setting back[i] to back[i-1] 1.

3. At the end of the loop, the longest sequence that can be constructed from the input array will be the maximum of front[n-1] and back[n-1].

int longest_sequence(int input[], int n)
{
    // Initialize dynamic programming arrays
    int front[n];
    int back[n];

    // Set all elements of the arrays to 1
    for (int i = 0; i < n; i  )
    {
        front[i] = 1;
        back[i] = 1;
    }

    // Iterate over the input array from left to right
    for (int i = 1; i < n; i  )
    {
        // If the current element is greater than the element at the front of the sequence,
        // append it to the front of the sequence by updating front[i]
        if (input[i] > input[front[i-1]])
        {
            front[i] = front[i-1]   1;
        }

        // If the current element is smaller than the element at the back of the sequence,
        // append it to the back of the sequence by updating back[i]
        if (input[i] < input[back[i-1]])
        {
            back[i] = back[i-1]   1;
        }
    }

    // Return the maximum of front[n-1] and back[n-1]
    return std::max(front[n-1], back[n-1]);
}

I tested my solution with your example:

int input[] = {6, 7, 3, 5, 4};
int n = 5;

int result = longest_sequence(input, n);

As you outlined (step-by-step) the longest sequence is {7, 6, 5, 4} of length 4. That is exactly the result that is being returned by longest_sequence!

This algorithm will take O(n^2) time to run, since you need to iterate over the input array and then over the dynamic programming arrays at each step. This is the best you can do, since any algorithm that solves this problem will need to examine every element in the input array at least once.

... Probably the biggest caveat of implementing the solution dynamically.