Cod sursa(job #1356906)

Utilizator fluture.godlikeGafton Mihnea Alexandru fluture.godlike Data 23 februarie 2015 17:27:11
Problema Subsir crescator maximal Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include <stdio.h>
#define NMAX 100023
#define inf 2000000023
FILE *fin, *fout;
int n, maxn, poz, dr, p, ans[NMAX], p1;
struct ceva
{
    int val;
    int pos;
} v[NMAX], d[NMAX], temp;
bool comp(ceva a, ceva b)
{
    return (a.val <= b.val);
}
int main()
{
    fin = freopen("scmax.in", "r", stdin);
    fout = freopen("scmax.out", "w", stdout);
    scanf("%d", &n);
    for(int i = 1; i<= n; ++i) scanf("%d", &v[i].val);
    d[0].val = inf;
    for(int i = 1; i<= n; ++i)
    {
    	while(v[i].val <= d[dr].val && dr >= 0)
    	{
    		dr--;
    	}
    	dr++;
    	d[dr].val = v[i].val;
    	d[dr].pos = i;
    	if(dr+1 > maxn)
    	{
    		maxn = dr+1;
    		p = i;
    	}
    	v[i].pos = d[dr-1].pos;
    	//for(int i = 0; i<= dr; ++i) printf("%d ", d[i].val);printf("\n");
    }
    printf("%d\n", maxn);
    fclose(fin);
    fclose(fout);
    return 0;
}