Pagini recente » Cod sursa (job #2755378) | Cod sursa (job #2525790) | Cod sursa (job #2690023) | Cod sursa (job #1073423) | Cod sursa (job #2399282)
#include <iostream>
#include <fstream>
#include <unordered_map>
#include <map>
#include <set>
#include <queue>
#include <list>
#include <numeric>
#include <stack>
#include <algorithm>
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;
}