package 最大的子数组和;

import java.util.Scanner;

public class shuzu {

	public static int maxArr(int a[]) {

		int max=a[0];

		for(int i=1;i<a.length;i++) {

			if(a[i]>max) {

				max=a[i];

			}

		}

		return max;

	}

	public static void main(String args[]) {

		/*

		 * 生成数组

		 */

		System.out.println("请输入数组里数字个数");

	    Scanner scan = new Scanner(System.in);

	    int num = scan.nextInt();

	    int[] array = new int[num];

	    System.out.println("请输入"+num+"个数值，空格间隔");

	    for(int i = 0;i < num;i++) {

	    	array[i] = scan.nextInt();

	    }

	    int lon = ((1+num)/2+1)*num;//存放所有子数组和的 数组

	    int[] sum = new int[lon];

	    int sumchangdu = 0;

	    int sumchangdu1  = 0;

	    /*求所有子数组的和   放进sum数组中*/

	    int[] maxarr = new int[num];//存放子数组和最大值的所有组成元素的数组

	    for(int i = 0;i < num;i++) {

	    	int[] arr = new int[num];//存放当前子数组和的所有组成元素的数组

	    	int asum = 0;

	    	int changdu = 0;

	    	for(int j = 0; j < num - i;j++) {

	    		arr[changdu] = array[i+j];

	    		asum = asum + array[i+j];

	    		sum[sumchangdu] = asum;

	    		sumchangdu1 = sumchangdu+1;

	    		System.out.println("当前执行第"+sumchangdu1+"步");

	    		System.out.println("第"+ sumchangdu1 +"个子数组和为:"+sum[sumchangdu]);

	    		System.out.print("组成当前的子数组和的元素为:");

	    		for(int y = 0; y < arr.length;y++) {

	    			if(arr[y]!=0)

	    			System.out.print(arr[y]+" ");

	    		}

	    		System.out.println("");

	    		if(sum[sumchangdu]==maxArr(sum)) {

	    			for(int k =0; k < arr.length;k++)

	    				maxarr[k] = arr[k];

	    		}

	    		System.out.println("前"+ sumchangdu1 +"个子数组和的最大值为:"+maxArr(sum));

	    		System.out.print("组成最大子数组和的元素为:");

	    		for(int x =0;x < maxarr.length;x++ ) {

	    			if(maxarr[x]!=0)

	    			System.out.print(maxarr[x]+"  ");

	    		}

	    		System.out.println("");

	    		System.out.println("输入0键开始执行下一步");

	    		int x = scan.nextInt();

	    		if(x==0) {

	    			System.out.println("--------------------------------------------");

		    		sumchangdu++;

		    		changdu++;

	    		}

	    		else {

	    			System.out.println("输入有误，程序退出！");
                                System.exit(0);

	    		}

	    	}

	    }

	   scan.close();

	    int max = sum[0];

	    for(int m = 1; m < lon;m++) {

	    	if(sum[m]>max)             //求sum数组最大的值

	    		max = sum[m];

	}

	    System.out.println("最大子数组和为:"+max);//输出最大的子数组和

	}

}