Cerința

Se dă un șir cu n elemente, numere întregi. Determinați secvența de elemente cu suma maximă.

Date de intrare

Fișierul de intrare secvsummax.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 secvsummax.out va conține pe prima linie numerele p și u, separate printr-un spațiu, reprezentând poziția de început și de sfârșit a secvenței determinate.

Restricții și precizări

• 1 ≤ n ≤ 100.000
• elementele șirului vor avea cel mult 4 cifre și sunt numerotate de la 1 la n
• dacă șirul conține mai multe secvențe de suma maximă, se va determina cea cu indicele de început cel mai mic, iar în caz de egalitate, cea mai scurtă
• șirul va conține cel puțin un element pozitiv

Exemplu

secvsummax.in

10
-4 1 -5 1 4 -2 2 3 -4 4

secvsummax.out

4 8

Explicație

Secvența 1 4 -2 2 3 are suma 8 și este suma maximă pentru toate secvențele care se pot forma.

#include <bits/stdc++.h>
using namespace std;
ifstream cin("secvsummax.in");
ofstream cout("secvsummax.out");
int n, a[100002];
int main()
{
    cin >> n;
    for(int i = 1 ; i <= n ; ++i)
        cin >> a[i];
    int s = 0 , d = 1 ,maxi = -2000000010 , sum=a[1] , p = 1;
    for(int i=2;i<=n;++i)
    {
        if(sum < 0) sum=a[i], p = i;
        else sum += a[i];
        if(sum > maxi)
        {
            maxi = sum;
            s = p;
            d = i;
        }
    }
    cout << s << " " << d;
    return 0;
}