import java.util.Scanner;

public class Aux2p1 {

	// invariante se conoce el segmento de suma maxima que comienza en algun indice anterior a i
	public static void segmentoMaximo(int[] arreglo) {
		int sumaMaxima = Integer.MIN_VALUE;
		int indiceInicio = -1;
		int indiceFin = -1;

		for(int i = 0; i < arreglo.length; i++) {
			// invariante se conoce el segmento de suma maxima que comienza con el i actual y termina en un indice anterior a j
			for(int j = i; j < arreglo.length; j++) {
				int suma = 0;
        
        // se suma el rango completo para cada iteración
				for (int k = i; k <= j; k++) {
					suma += arreglo[k];
				}
				if(suma > sumaMaxima) {
					sumaMaxima = suma;
					indiceInicio = i;
					indiceFin = j;
				}
			}
		}
		System.out.println("sumaMaxima = " + sumaMaxima);
		System.out.println("indiceInicio = " + indiceInicio);
		System.out.println("indiceFin = " + indiceFin);
	}

	public static void segmentoMaximo2(int[] arreglo) {
		int sumaMaxima = Integer.MIN_VALUE;
		int indiceInicio = -1;
		int indiceFin = -1;

		// invariante se conoce el segmento de suma maxima que comienza en algun indice anterior a i
		for(int i = 0; i < arreglo.length; i++) {
			int sumaActual = 0;
      
			for(int j = i; j < arreglo.length; j++) {
        
        // se ocupa la suma anterior para obtener la suma del rango actual
				sumaActual += arreglo[j];

				if(sumaActual > sumaMaxima){
					sumaMaxima = sumaActual;
					indiceInicio = i;
					indiceFin = j;
				}
			}
		}
		System.out.println("sumaMaxima = " + sumaMaxima);
		System.out.println("indiceInicio = " + indiceInicio);
		System.out.println("indiceFin = " + indiceFin);
	}

	// invariante se conoce el segmento de suma maxima contenido antes del indice i
	public static void segmentoMaximo3(int[] arreglo) {
		int sumaMaxima = Integer.MIN_VALUE;
		int indiceInicioActual = 0;
		int indiceInicio = 0;
		int indiceFin = -1;

		int sumaActual = 0;
		for(int i = 0; i < arreglo.length; i++) {
			
			sumaActual += arreglo[i];
      
			if(sumaActual > sumaMaxima){
				sumaMaxima = sumaActual;
				indiceInicio = indiceInicioActual;
				indiceFin = i;
			}
			else if(sumaActual < 0){
				sumaActual = 0;
				indiceInicioActual = i + 1;
			}
		}
    
		System.out.println("sumaMaxima = " + sumaMaxima);
		System.out.println("indiceInicio = " + indiceInicio);
		System.out.println("indiceFin = " + indiceFin);
	}

	public static void main(String[] args) {
		int[] arreglo = {1, 2, 3,-7, 2, 8, 50, -20, -100, 7, -1, -3, 0, 48, 10, 5};
		segmentoMaximo(arreglo);
		segmentoMaximo2(arreglo);
		segmentoMaximo3(arreglo);
    
    System.out.println("\nIngrese un arreglo de enteros separados por espacio");
		Scanner in = new Scanner(System.in);
		
		// "2 4 87 2 -1 -3"
		String input = in.nextLine();
    
		String[] partes = input.split(" ");
		int[] a = new int[partes.length];
		
		for (int i = 0; i < a.length; i++) {
			a[i] = Integer.parseInt(partes[i]);
		}
		
		segmentoMaximo3(a);
	}

}