Running lists

running_lists.cpp

bool ShouldSwap(std::vector<int> list, int i)
{
  bool more_than_one_val   = (list.size() > 1);
  bool last_value_bigger   = (list.back() > i);
  bool second_last_smaller = (list[list.size() - 2] < i);
  
  return (more_than_one_val && last_value_bigger && second_last_smaller);
}

void TestLists()
{
  std::vector<int>                          input{10, 12, 4, 6, 100, 2, 56, 34, 79, 45, 33, 12, 45, 67, 89};
  std::unordered_map<int, std::vector<int>> lists;
  int                                       top_index{}, biggest_size{};
  std::unordered_map<int, int>              indexes{};         // Max value for each running list

  for (int i : input)
  {
    if (lists.find(i) == lists.end())
    {
      lists  .insert({i, std::vector<int>{i}});
      indexes.insert({i, i});
    }

    for (auto& [index, max] : indexes)
    {
      if (i > max)
      {
        lists  .at(index).emplace_back(i);
        indexes.at(index) = i;

        if (lists.at(index).size() > biggest_size)
        {
          top_index    = index;
          biggest_size = lists.at(index).size();
        }
      }
      else
      {
        auto& list = lists.at(index);
        if (ShouldSwap(list, i))
        {
          list.back()       = i;
          indexes.at(index) = i;
        }
      }
    }
  }
  
  assert(biggest_size == lists.at(top_index).size());
}