返回一个整数数组中最大子数组的和。

一、程序题目

　　返回一个整数数组中最大子数组的和。

二、程序要求

　　1、输入一个整型数组，数组里有正数也有负数；

　　2、数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和；

　　3、求所有子数组的和的最大值，要求时间复杂度为O(n)。

三、程序设计思想

　　1、数组的长度和各个元素由键盘键入；

　　2、先将各元素累加，每加一个数，看结果是否为0，若为0，重置结果，并且结果与最大子数组和（简称最大和）比较，若有更大的和，就保存较大的结果到最大和中；

　　3、若最大和与结果的值均为0，说明数组为负数数组，最大子数组即为最大元素。

import java.util.Scanner;
//2023.03.06
//20214128
public class sum {

    public static void main(String[] args) {
            int arrlength, i;
            int maxsum = 0, sum = 0;
            int arr[]=new int[100];
            Scanner sr=new Scanner(System.in);
            System.out.print("请输入数组长度：");
            arrlength=sr.nextInt();
            if (arr == null || arrlength == 0)
            {
                //exit(1);
                System.out.print("数组为空");
               return ;
            }

            System.out.print( "请输入数组元素：");
            for (i = 0; i<arrlength; i++)
            {    
                if(sr.hasNextInt())                
                    arr[i]=sr.nextInt();
                else
                    {
                    System.out.print("非法输入，录入结束");
                    return ;
                    }
                 
            }
            maxsum = 0;
            sum = 0;
            for (i = 0; i<arrlength; i++)
            {
                sum = sum + arr[i];//累加

                if (sum<0)      //当前和小于0，重置为0
                {
                    sum = 0;
                }

                if (sum>maxsum) // 当前和大于最大和，则重置最大和
                {
                    maxsum = sum;
                }
            }

            if (maxsum == 0)      //maxsum=0,说明数组中的数值均为负数
            {
                maxsum = arr[0];
                for (i = 1; i<arrlength; i++)
                {
                    if (arr[i]>maxsum)//求出负数数组的最大值
                    {
                        maxsum = arr[i];
                    }
                }
            }
            System.out.print("最大子数组的和为：" );

            System.out.print(maxsum);
    
    }

}