Cod sursa(job #2399280)

Utilizator Tux2NicolaeTelechi Nicolae Tux2Nicolae Data 7 aprilie 2019 11:36:06
Problema Subsir crescator maximal Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.73 kb
#include <iostream>
#include <fstream>
#include <unordered_map>
#include <map>
#include <set>
#include <queue>
#include <list>
#include <numeric>
#include <stack>
#include <algorithm>
#include <intsafe.h>

using namespace std;

int main()
{
  ifstream in("scmax.in");
  ofstream out("scmax.out");

  struct SequenceElement {
    int nr{};
    int maxSubsequence{};
    int previousIndex{};
  };

  vector<SequenceElement> numbers;

  // insert dummy number on the 0 index
  numbers.push_back({});

  int n = 0;
  in >> n;

  if (n == 0)
    return 1;

  // calculate the maximum subsequence
  for (int i = 1; i <= n; ++i)
  {
    int x = 0;
    in >> x;

    SequenceElement element;
    element.nr = x;
    element.maxSubsequence = 0;
    element.previousIndex = 0;
        
    for (int j = 0; j < i; ++j)
    {
      if (numbers[j].nr < element.nr && numbers[j].maxSubsequence + 1 > element.maxSubsequence)
      {
        element.maxSubsequence = numbers[j].maxSubsequence + 1;
        element.previousIndex = j;
      }
    }

    numbers.push_back(element);
  }
  
  // print numbers
  auto it = max_element(begin(numbers), end(numbers), [](const auto & first, const auto & second) {
    return first.maxSubsequence < second.maxSubsequence;
  });

  if (it == end(numbers))
    return 1;
 
  out << it->maxSubsequence << endl;

  stack<int> items;

  int currentIndex = distance(begin(numbers), it);
  while (currentIndex != 0)
  {
    const auto & currentElement = numbers[currentIndex];

    items.push(currentElement.nr);
    currentIndex = numbers[currentIndex].previousIndex;
  }

  while (!items.empty())
  {
    out << items.top() << " ";
    items.pop();
  }

  return 0;
}