首页 > 代码库 > 求一个数组的最大子数组之和
求一个数组的最大子数组之和
题目:
输入一个一维整形数组,数组里有正数也有负数。一维数组首尾相接,像个一条首尾相接带子一样。数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和。求所有子数组的和的最大值。
代码:
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; } }
求一个数组的最大子数组之和
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。