Cod sursa(job #132458)

Utilizator gabitzish1Gabriel Bitis gabitzish1 Data 5 februarie 2008 21:08:50
Problema Secventa 2 Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.63 kb
//Subsecventa de suma maxima de lungime >= L, complexitate O(n), varianta 1
#include <stdio.h>
int n, v[50001], max, l;

int main()
{
   freopen("secv2.in","r",stdin);
   freopen("secv2.out","w",stdout);

   int i, sc, pi, pf, p;

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

   p = pi = pf = 1;
   sc = max = v[1];

   for (i = 2; i <= n; i++)
   {
      if (sc < 0)
      {
	 sc = v[i];
	 p = i;
      }
      else sc += v[i];

      if (max < sc && i - p + 1 >= l)
      {
	 max = sc;
	 pi = p;
	 pf = i;
      }
   }

   printf("%d %d %d\n", pi, pf, max);
   return 0;
}