Cod sursa(job #825104)

Utilizator cristalCiurdarean Andrei cristal Data 27 noiembrie 2012 14:55:02
Problema Secventa 2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.98 kb
// 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;
}