/*（没写若全负数的情况）
* 题目：有一个数字串array,包含100个正数和负数随机分布，
* 要找到他的一个子串array[i...j](0<=i<=j<=100),
* 使得在array的所有子串中，array[i...j]的和最大。
* 比如：串{1,-3,5,-2,6}的最大子串为{5,-2,6}。
* */
public class Maxmum {
        public static void main(String[] args) {
                int[] arr=new int[100];
                int b = 0,sum=0,k=0;
                int start = 0,end = 0;
                //产生（-100,100）的整数
                for(int i=0;i<5;i++){
                        arr[i] =((Math.random() > 0.5 ? -1 : 1) * (int) (Math.random() * 100));
                         if (i % 10 == 0) {
                 System.out.println();
         }
         System.out.print(arr[i] + " ");
                }
                //遍历数组，求最大值
                for (int i=0; i<arr.length; i++) {
                                 b=b+arr[i];
                                 if(b>sum){
                                         sum=b;
                                         start=k;
                                         end=i;
                                }
                                if(b<0)
                                        {   
                                                b=0;
                                                k=i+1;
                                        }
                        }       
                System.out.println();
                System.out.println("最大子串和："+sum);
                System.out.println("下标从"+start+"开始"+" "+"从"+end+"结束");
                System.out.print("最大子串：");
                for(int i=start;i<=end;i++){
                        System.out.print(arr[i]+" ");
                }
        }
}

/*（没写若全负数的情况）
* 题目：有一个数字串array,包含100个正数和负数随机分布，
* 要找到他的一个子串array[i...j](0<=i<=j<=100),
* 使得在array的所有子串中，array[i...j]的和最大。
* 比如：串{1,-3,5,-2,6}的最大子串为{5,-2,6}。
* */
public class Maxmum {
        public static void main(String[] args) {
                int[] arr=new int[100];
                int b = 0,sum=0,k=0;
                int start = 0,end = 0;
                //产生（-100,100）的整数
                for(int i=0;i<5;i++){
                        arr[i] =((Math.random() > 0.5 ? -1 : 1) * (int) (Math.random() * 100));
                         if (i % 10 == 0) {
                 System.out.println();
         }
         System.out.print(arr[i] + " ");
                }
                //遍历数组，求最大值
                for (int i=0; i<arr.length; i++) {
                                 b=b+arr[i];
                                 if(b>sum){
                                         sum=b;
                                         start=k;
                                         end=i;
                                }
                                if(b<0)
                                        {   
                                                b=0;
                                                k=i+1;
                                        }
                        }       
                System.out.println();
                System.out.println("最大子串和："+sum);
                System.out.println("下标从"+start+"开始"+" "+"从"+end+"结束");
                System.out.print("最大子串：");
                for(int i=start;i<=end;i++){
                        System.out.print(arr[i]+" ");
                }
        }
}