Dynamic Programming - Longest Increasing Sequence (C++)

lis.cc

/*
 * Dynamic programming practice question - Longest Increasing Subsequence (LIS)
 */

#include <map>
#include <vector>
#include <utility>

#include "utils.h"

#define map std::map
#define vec std::vector

// `lis_len` just computes the length of the longest increasing sequence.
template<typename T>
int lis_len(const vec<T> &v) {
  vec<int> lis_subproblems;
  lis_subproblems.reserve(v.size());
  int max_ever = 0;
  for (int i = 0; i < v.size(); ++i) {
    int max_subproblem = 0;
    for (int j = 0; j < i; ++j)
      if (v[j] < v[i] && max_subproblem < lis_subproblems[j])
        max_subproblem = lis_subproblems[j];

    lis_subproblems[i] = ++max_subproblem;
    if (max_ever < max_subproblem) max_ever = max_subproblem;
  }
  return max_ever;
}

// `lis_indices` computes the indices of a longest increasing sequence in the
// vector `v`. The returned indices are in reverse order i.e. from largest
// element to smallest element.
template<typename T>
vec<int> lis_indices(const vec<T> &v) {
  // lis_subproblems keeps track of the maximum lis_length until an index as
  // well as the previous index in that subsequence
  map<int, std::pair<int, int> > lis_subproblems;
  // these two variables store the global maxes (length of longest subsequence
  // found and the index at which it terminates)
  int max_ever = 0; int max_ever_idx = -1;
  // solve each subproblem up to the last element
  for (int i = 0; i < v.size(); ++i) {
    int max_subproblem = 0; int prev_idx = -1;
    for (int j = 0; j < i; ++j)
      if (v[j] < v[i] && max_subproblem < lis_subproblems[j].first) {
        max_subproblem = lis_subproblems[j].first;
        prev_idx = j;
      }
    lis_subproblems[i] = std::pair<int, int>(++max_subproblem, prev_idx);
    // if the subproblem we just solved is better than the global maxes found
    // so far, replace the global maxes
    if (max_ever < max_subproblem) {
      max_ever = max_subproblem;
      max_ever_idx = i;
    }
  }
  // compile the resulting LIS indices
  vec<int> lis;
  int curr_idx = max_ever_idx;
  while (curr_idx != -1) {
    lis.push_back(curr_idx);
    curr_idx = lis_subproblems[curr_idx].second;
  }
  return lis;
}