Cod sursa(job #2308245)

Utilizator Dragne.Andrei11Dragne Andrei Dragne.Andrei11 Data 26 decembrie 2018 18:25:34
Problema Subsir crescator maximal Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.8 kb
#include <bits/stdc++.h>
#define nmax 100005

using namespace std;

stack <int> poz;
int rasp[nmax];

int a[nmax];

int main()
{
    freopen("scmax.in", "r", stdin);
    freopen("scmax.out", "w", stdout);
    int n;

    scanf("%d", &n);
    for(int i=1;i<=n;i++)
        scanf("%d", &a[i]);
    for(int i=1;i<=n;i++)
    {
        int maxim=rasp[i-1];
        if(poz.size()==0)
        {
            poz.push(i);
            rasp[i]++;
            continue;
        }
        else
        {
            while(a[poz.top()]<a[i]&&poz.size()>0)
            {
                maxim=max(rasp[poz.top()]+1, maxim);
                poz.pop();
            }
            poz.push(i);
            rasp[i]=max(maxim, 1);
        }
    }
    printf("%d\n", rasp[n]);

    return 0;
}