import java.io.*;
import java.util.*;

public class Algo134
{
       private static int[] a;

       private static int Eingabe()
       {
               int i=0;
               while (i<=0)
               {  
                  try
                  {
                      BufferedReader Input = new BufferedReader(
                                             new InputStreamReader(System.in));
                      System.out.print("Bitte n eingeben: ");
                      i = Integer.parseInt(Input.readLine());
                  }
                  catch (Exception e)
                  {
                       System.out.println("Fehler in Eingabe(): "+e);
                  }
               }
              	return i;
       }

       private static void Initialisierung(int m)
       {
               a = new int[m];
               Random Zufallszahl = new Random(8);
               for (int i=0; i<m; i++)
               {
                   a[i] = (Zufallszahl.nextInt() % 4793) - 2396;
               }
       }

       public static void main(String args[])
       {
              int A,B,n;
		    n = Eingabe();
              Initialisierung(n);
              Date Anfang = new Date();
              A = a[0];
              B = a[0];
              for (int i=1; i<n; i++)
              {
                  B = Math.max(B+a[i], a[i]);
                  A = Math.max(A,B);
              }
              Date Ende = new Date();
              System.out.println("Der Wert des maximalen Intervalls ist " + A);
              System.out.println("Laufzeit: " + 
				(Ende.getTime() - Anfang.getTime()) + " (msec) ");
       }
}