Se consideră un șir A cu N elemente întregi nenule. Numim secvență a șirului A orice succesiune de elemente aflate pe poziții consecutive în șir: A_i, A_i+1, …, A_j cu 1 ≤ i < j ≤ N. Prin lungimea secvenței înțelegem numărul de elemente care o compun.

Pentru orice secvenţă A_i, A_i+1, …, A_j, vom numi split-point un indice k, i ≤ k < j, care împarte secvența în două subsecvențe nevide: A_i, A_i+1, …, A_k, respectiv A_k+1, A_k+2, …, A_j.

Fie Dmax valoarea absolută maximă a diferenței sumelor elementelor celor două subsecvențe separate de un split-point, luând în considerare toate secvenţele Ai,Ai+1,…,Aj posibile şi fie Lmax lungimea maximă a unei secvenţe caracterizată de valoarea Dmax.

Cerinţă

Cunoscând N şi valorile elementelor şirului A, să se determine Dmax şi Lmax.

Date de intrare

Fișierul de intrare ksplit.in conține pe prima linie un număr natural N ce reprezintă numărul de elemente al șirului A, iar pe cea de-a doua linie N numere întregi nenule despărțite prin câte un spațiu.

Date de ieșire

Fișierul de ieșire ksplit.out va avea două linii. Prima linie conține numărul natural Dmax iar următoarea linie conţine numărul natural Lmax.

Restricții și precizări

2 ≤ N ≤ 100 000
elementele șirului A sunt numere întregi nenule din intervalul [-1 000 000, 1 000 000]

Exemplu

ksplit.in

4
2 3 -1 5

ksplit.out

6
3

Explicație

Dintre toate secvențele ce se pot forma, se alege secvența 2 3 -1, care este formată din primele 3 elemente ale șirului.

Valoarea Dmax este 6, adică: s1 = 2 + 3 = 5, s2 = -1, Dmax = |5 – (-1)|=6, Lmax = 3.

Se observă că există și secvența -1 5 pentru care : s1 = -1, s2 = 5, Dmax = |-1 – 5|=6 dar această secvență are lungimea 2.

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema ksplit:

/*
    Solutie subsecventa de suma maxima/minima
    Complexitate: O(N)
    prof. Eugen Nodea
*/
# include <fstream>
# include <climits>
# include <cmath>
# define NMax 100003
using namespace std;

int i, n, Lmax;
int a[NMax];
long long Max = -LONG_MAX;
long long smax[NMax], smin[NMax];
int pozM[NMax];
int pozm[NMax];

void ssm_st_dr(long long smax[NMax], int poz[NMax], int semn)
{
    smax[1] =  a[1]; poz[1] = 1;
    for (int i=2; i<=n; ++i)
    {
        if (semn * smax[i-1] >= 0)
        {
            smax[i]  = a[i] + smax[i-1];
            poz[i] = poz[i-1];
        }
        else
        {
            smax[i]  = a[i];
            poz[i] = i;
        }
    }
}
void ssm_dr_st(long long smax[NMax], int poz[NMax], int semn)
{
    smax[n-1] = a[n]; poz[n-1] = n;
    for (int i=n-2; i>0; --i)
    {
        if (semn * smax[i+1] >= 0)
        {
            smax[i]  = a[i+1] + smax[i+1];
            poz[i] = poz[i+1];
        }
        else
        {
            smax[i]  = a[i+1];
            poz[i] = i+1;
        }
    }
}
void sol(long long smax[NMax], long long smin[NMax], int pozM[NMax], int pozm[NMax], int semn)
{
    for (int i=1; i<n; ++i)
    {
        long long x = semn * (smax[i] - smin[i]);
        if (x > Max)
        {
            Max = x;
            Lmax = semn * (pozM[i] - pozm[i]);
        }
    }
}
int main()
{
    freopen("ksplit.in", "r", stdin);
    freopen("ksplit.out","w", stdout);

    scanf("%d", &n);

    for (i=1; i<=n; ++i)
        scanf("%d", &a[i]);

    ssm_st_dr(smax, pozM, 1);
    ssm_dr_st(smin, pozm, -1);
    sol(smax, smin, pozm, pozM, 1);

    ssm_st_dr(smax, pozM, -1);
    ssm_dr_st(smin, pozm, 1);
    sol(smax, smin, pozM, pozm, -1);

    printf("%lld
%d
", Max, Lmax + 1);

    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #680 ksplit

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #680 ksplit de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #680 ksplit