Cerinţa

Se dă un şir cu n elemente, numere naturale. Determinaţi cea mai lungă secvenţă de elemente din şir cu proprietatea că oricare două valori consecutive în secvenţă au parităţi diferite.

Dacă există mai multe secvente de lungime maximă cu această proprietate, se va determina aceea cu suma elementelor maximă. Dacă există mai multe secvenţe de lungime maximă cu aceeaşi sumă maximă a elementelor se va determina cea mai din dreapta.

Date de intrare

Fişierul de intrare secventa.in conţine pe prima linie numărul n; urmează cele n elemente ale şirului, dispuse pe mai multe linii şi separate prin spaţii.

Date de ieşire

Fişierul de ieşire secventa.out va conţine pe prima linie două numere p şi u, separate printr-un spaţiu, reprezentând indicele primului, respectiv al ultimului element din secvenţa determinată.

Restricţii şi precizări

• 1 ≤ n ≤ 100.000;
• elementele şirului vor avea cel mult 9 cifre şi sunt numerotate de la 1 la n;

Exemplu

secventa.in

10
2 4 3 6 7 5 2 5 8 10

secventa.out

6 9

Explicație

Există două secvenţe de elemente care respectă regula precizată de lungime maximă. Suma elementelor din cele două secvenţe este aceeaşi, astfel că s-a afişat secvenţa cea mai din dreapta.

#include <bits/stdc++.h>

using namespace std;

ifstream cin("secventa.in");
ofstream cout("secventa.out");

int main()
{
    int n;
    cin >> n;
    int a[100001];
    for(int i = 1; i <= n; ++i)
        cin >> a[i];

    int lmax = 1, l = 1, st = 1, dr = 1, summax = a[1], sum = a[1];
    for(int i = 2; i <= n; ++i){
        if(a[i] % 2 != a[i-1] % 2){
            l++;
            sum += a[i];
        }
        else{
            if(l > lmax)
                lmax = l, st = i - l, dr = i - 1, summax = sum;
            else if(l == lmax)
                if(sum >= summax)
                    summax = sum, st = i - l, dr = i - 1;
            l = 1, sum = a[i];
        }
    }
    if(l > lmax)
        lmax = l, st = n - l + 1, dr = n, summax = sum;
    else if(l == lmax)
        if(sum >= summax)
            summax = sum, st = n - l + 1, dr = n;

    cout << st << ' ' << dr;

    return 0;
}