Pagini recente » Cod sursa (job #2939247) | Cod sursa (job #2164002) | Cod sursa (job #1934998) | Cod sursa (job #762619) | Cod sursa (job #825104)
Cod sursa(job #825104)
// Cea mai lunga secventa cu elemente in ordine crescatoare
// Complexitate O(n)
#include <fstream>
using namespace std;
ifstream is("1.in");
ofstream os("1.out");
int a[50000];
int n, k;
int main()
{
is >> n >> k;
for ( int i = 0; i < n; i++)
is >> a[i];
int Lmax = 0;
int S, D;
int p1 = 0, p2 = 0; // pozitiile stanga si dreapta a capetelor secventei curente
int L = 1; // a[0] face parte sin secventa initiala
for ( int i = 1; i < n; i++)
{
if ( a[i-1] < a[i] ) // cat timp imi este indeplinita conditia
{
L++; // cresc lungimea
p2 = i; // memorez capatul din dreapta a secventei
if ( L > Lmax ) // compar cu maximul
{
Lmax = L;
S = p1;
D = p2;
}
}
else // conditia nu este indeplinita
{
L = 1; // incep numaratoarea
p1 = i; // mut marginea stanga pe i
}
}
if ( p1 - p2 > k )
os << p1 << " " << p2 << " " << Lmax << ;'\n';
is.close();
os.close();
return 0;
}