首页 > 代码库 > 整数数组求最大子数组和
整数数组求最大子数组和
一、实验题目
返回一个整数数组中最大子数组的和。
二、实验要求
输入一个一维整形数组，数组里有正数也有负数。
一维数组首尾相接，象个一条首尾相接带子一样。
数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。求所有子数组的和的最大值。
三、设计思想
该实验大部分可以分为两部分：
1、利用while循环录入输入的数组值，输入值为string类型，利用Integer.parseInt(String a)，存入int数组，如果是"#"则结束录入
2、调用求最大值函数和的最大值，分为两部分：
1、先求一个直线数组的连续和的最大值，算法复杂度为o(n)（1）如果a,b>0，则a+b肯定>a。（2）如果a,b>0，c<0，所以a+b+c肯定<a+b。（3）如果a<0，b>0，所以b肯定大于a+b。所以当前一个数和小与零时，则赋值为零，再加下一个数，如果不是则与最大值比较，如果比最大值大，则更新最大值。当最后sum=0时，只有两种情况一个是数组中连续和最大值为0，另一种就是所有数都小于零。
2、求环的的连续和的最大值，即将最后一项的下一个为第一个数，即下标超出范围则减去数组的长度。利用for循环执行n次，遍历出最终的最大值，然后输出。
四、出现的问题
1、在循环遍历n次时，衔接不正确。
五、可能的解决方案（多选）
列出所有的情况，求出和，选出最大的值输出。
六、源代码
import java.util.Scanner;
public class Max
{
public static void main(String[] args)
{
int shu[]=new int[100];
int k=0;
Scanner scanner=new Scanner(System.in);
System.out.println("请输入若干个整数：");
String a=scanner.next();
if(a.equals("#")) System.out.println("您什么都没有输入，故没有最大值！");
else
{
shu[k]=Integer.parseInt(a);
k++;
a=scanner.next();
while(!a.equals("#"))
{
shu[k]=Integer.parseInt(a);
k++;
a=scanner.next();
}
System.out.println("数组中连续数的最大值为："+MaxSum(shu,k));
}
}
static int MaxSum(int[] arr,int k)
{
int Sum=0;
int maxSum=0;
int len=k;
int d;
int i;
int j;
for(j=0;j<len;j++)
{
for (i=j;i<len+j;i++)
{
if(i>len-1) d=i-len;
else d=i;
Sum+=arr[d];
if(Sum<0)
{
Sum=0;
}
if(Sum>maxSum)
{
maxSum=Sum;
}
}
Sum=0;
}
if(maxSum==0)
{
for(i=0;i<len;i++)
{
if(i==0)
{
maxSum=arr[i];
}
if(arr[i]>maxSum)
{
maxSum=arr[i];
}
}
}
return maxSum;
}
}
七、结果截图
八、总结
此程序没有进行最终的优化。
整数数组求最大子数组和
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。