Pagini recente » Cod sursa (job #3136075) | Cod sursa (job #3122927) | Cod sursa (job #1103129) | Cod sursa (job #1481007) | Cod sursa (job #2121451)
#include <fstream>
#include <vector>
#include <set>
std::ifstream f("scmax.in");
std::ofstream g("scmax.out");
unsigned int n;
unsigned int v[100001];
std::vector<unsigned int> length(100001, 1);
unsigned int pos[100001];
unsigned int maxLength;
unsigned int maxLengthIndex;
struct element
{
unsigned int index;
unsigned int length;
bool operator > (const element& other) const
{
if (this->length > other.length)
return true;
return false;
}
bool operator < (const element& other) const
{
if (this->length < other.length)
return true;
return false;
}
};
std::set<element> lengths;
void Read()
{
f >> n;
for (int i = 1; i <= n; ++i)
{
f >> v[i];
}
}
void modify(unsigned int i)
{
unsigned int j = i + 1;
unsigned int maxIndex = 0;
element el = { i + 1, length[i + 1] };
/*
for (; j <= n; ++j)
{
if (v[j] > v[i] && length[j] > max)
{
max = length[j];
maxIndex = j;
}
}*/
if(v[i + 1] > v[i])
lengths.insert(el);
if (!lengths.empty())
{
length[i] = 1 + (lengths.rbegin())->length;
maxIndex = lengths.rbegin()->index;
}
else
{
length[i] = 1;
maxIndex = i;
}
if (length[i] > maxLength)
{
maxLength = length[i];
maxLengthIndex = i;
}
pos[i] = maxIndex;
}
void Solve()
{
unsigned int i;
for (int i = n - 1; i > 0; --i)
{
modify(i);
}
g << maxLength << "\n";
for (i = maxLengthIndex; pos[i] != 0; i = pos[i])
{
g << v[i] << " ";
}
g << v[i];
g << "\n";
}
int main()
{
Read();
Solve();
return 0;
}