Участник:ZhenyaStrelkova/ALTSEQ

Материал из DISCOPAL
Перейти к: навигация, поиск

https://www.spoj.com/problems/ALTSEQ/

#include <iostream>
#include <cstdlib>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int main() {
    int N = 0;
    cin >> N;
    vector<int> sequence(N);
    vector<int> signs;
    vector<int> altSeq(N);
 
    for(int i = 0; i < N; i ++)
        cin >> sequence[i];
    for(auto const& elem: sequence){
        signs.push_back(elem < 0 ? 1 : 0);
    }
    for(int i = 0; i < N; i ++){
        for(int j = 0; j < i; j ++)
            if(signs[i] != signs[j] && abs(sequence[i]) > abs(sequence[j]))
                altSeq[i] = max(altSeq[i], altSeq[j] + 1);
        if(altSeq[i] == 0)
            altSeq[i] = 1;
    }
    cout << *max_element(altSeq.begin(), altSeq.end()) << endl;
 
    return 0;
}