# PBinfo #4241 – max2secv – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: deivid

## Enunț

Se dă un șir a1, a2, …, an de numere întregi. Definim suma unei secvențe ai, ai+1, …, aj ca fiind suma elementelor sale, adică ai + ai+1 + ... + aj.

Cerința
Să se determine suma maximă posibilă care se poate obține din două secvențe disjuncte din șir.

Date de intrare
Programul citește de la tastatură numărul n, iar apoi șirul de n numere întregi, separate prin spații.

Date de ieșire
Programul va afișa pe ecran numărul S, reprezentând suma maximă care se poate obține din două secvențe disjuncte.

Restricții și precizări

2 ≤ n ≤ 100.000
-100 ≤ a[i] ≤ 100
Două secvențe sunt disjuncte dacă nu au niciun element comun.

Exemplul 1:
Intrare

6
2 -1 3 -8 4 -5
Ieșire

8
Explicație
Cele două secvențe care dau suma maximă sunt 2 -1 3 și 4.

Exemplul 2:
Intrare

4
1 2 3 4
Ieșire

10
Explicație
Secvențele pot fi 1 2 și 3 4.

## Cod sursă C++

```cpp
#include <bits/stdc++.h>
using namespace std;
int a[100001], sp[100001], n;
int main()
{
    int i, smax, s, sTotal;
    cin >> n;
    for (i = 0; i < n; i++)
        cin >> a[i];
    s = sp[0] = a[0];
    if (s < 0) s = 0;
    for (i = 1; i < n; i++)
    {
        s += a[i];
        sp[i] = max(sp[i - 1], s);
        if (s < 0) s = 0;
    }
    s = smax = a[n - 1];
    if (s < 0) s = 0;
    sTotal = smax + sp[n - 2];
    for (i = n - 2; i > 0; i--)
    {
        s += a[i];
        if (smax < s) smax = s;
        if (s < 0) s = 0;
        sTotal = max(sTotal, smax + sp[i - 1]);
    }
    cout << sTotal;
    return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/4241)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/4241/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-4241/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)