首页 > 代码库 > 求一个数组的最大子数组之和

求一个数组的最大子数组之和

题目:

      输入一个一维整形数组,数组里有正数也有负数。一维数组首尾相接,像个一条首尾相接带子一样。数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和。求所有子数组的和的最大值。

代码:

import java.util.Scanner;

public class Array{

    public static void main(String[] args) {
        
        System.out.print("请输入数组的长度N=");
        Scanner scan=new Scanner(System.in);
        int length=scan.nextInt();
        int arr[]=new int[length];
        for(int i=0;i<length;i++){
            arr[i]=(int)(10-Math.random()*20);  //产生-10到10的随机数
        }
        
        int arr2[]=new int[2*length];
        for(int i=0;i<2*length;i++){
            if(i<length){
            	arr2[i]=arr[i];
            }
            else{
                arr2[i]=arr[i-length];
            }
        }
        
        System.out.print("数组:{ ");
        for(int i=0;i<length;i++){
        	System.out.print(arr[i]+" ");
        }    //用于验证数组
        System.out.println("}");
        
        int max=0;
        int curSum=0;
        int M[]=new int[length];
        for(int s=0;s<length;s++){
        	
        	for(int j=s;j<s+length;j++){
        		if(j==s){
        			max=arr2[j];
        			curSum=max;
        			continue;
                }
        		if(curSum<0){
        			curSum=0;
        		}
            
        		curSum+=arr2[j];
        		if(curSum>max){
        			max=curSum;
        		}
            }
        	M[s]=max;
        }
        int LL=Largest(M,length);
        System.out.println("最大子数组的和为:"+LL);
    }
    public static int Largest(int list[],int length)
    {
        int i,max=list[0];

        for(i=0;i<=length-1;i++)
        {
            if(list[i]> max){
                max=list[i];
            }
        }    
        return max;
    }
}

  

求一个数组的最大子数组之和