Advertisement
Worg99

Subsecventa de suma maxima

Oct 25th, 2014
179
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.97 KB | None | 0 0
  1. #include <cstdio>
  2. #define Nmax 100000
  3. using namespace std;
  4. FILE *fin = freopen("suma.in", "r", stdin);
  5. FILE *fout = freopen("suma.out", "w", stdout);
  6. int V[Nmax], N;
  7.  
  8.  
  9. int main()
  10. {
  11.     scanf("%d", &N);
  12.     for(int i = 1 ; i <= N ; ++i )
  13.         scanf("%d", &V[i]);
  14.     int p1 = 1 , p2 = 1, S = V[1], Smax = V[1], last = 1; // Am initializat elementele
  15.     // In variabila last memoram indicele de unde incepe secventa curenta, atat timp cat este pozitiva.
  16.     if( S < 0 )
  17.     {
  18.         S = 0;
  19.         last = 2;
  20.     }
  21.     for(int i = 2 ; i <= N ; ++i )
  22.     {
  23.         S += V[i]; // Marim S cu numarul curent
  24.         if( S > Smax ) // Verificam daca suma curenta, adica S, este mai mare ca Smax
  25.         {
  26.             Smax = S;
  27.             p1 = last;
  28.             p2 = i;
  29.         }
  30.         if( S < 0 ) // Daca S < 0 , atunci il facem 0.
  31.         {
  32.             S = 0;
  33.             last = i + 1;
  34.         }
  35.     }
  36.     printf("%d %d\n%d", p1, p2, Smax);
  37.     return 0;
  38. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement