题目:返回一个整数数组中最大子数组的和。
要求： 输入一个整形数组，数组里有正数也有负数。 数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。 求所有子数组的和的最大值。要求时间复杂度为O(n)
一设计思路（课堂时参照班内徐利峰同学的）
1.参照徐利峰同学的算法，首先可知输入整型数字时，第一个数字为一组；
从第二个数字开始，有两种可能，a[i]+a[i-1]>a[i]，即该数与之前一个数相加大于该数时，该数输出该数与前一个之和a[i]+a[i-1]；
否则输出该数a[i];
然后再新得出的a[i]中找出最大的数即为所求；
2.在此基础上定义数组，总数，用for循环依次输入并输出总数个整型数字，代入上述的算法中得出结果。
二出现的问题
暂时未知；
三可能的解决方案
暂时没有；
四源代码
package 数组;
import java.util.Scanner;
public class Shuzu {
public static void main(String[] args) {
int[] shu = new int [100];
@SuppressWarnings("resource")
Scanner sc=new Scanner(System.in);
System.out.println("请输入总数：");
int sum = sc.nextInt();
System.out.println("请输入"+sum+"个整型数字");
for(int i=0;i<sum;i++) {
shu[i] = sc.nextInt();
System.out.println("第"+(i+1)+"个是："+shu[i]) ;
}
int max = MaxSum(shu,sum);
System.out.println("所有子数组的和的最大值为:"+max);
}
static int MaxSum(int[] a,int length) {
int i=0;
int len = length;
for(i=1;i<len;i++){
if(a[i]+a[i-1]>a[i]) {
a[i]=a[i]+a[i-1];
}
}
int ans=-100000;
for(i=0;i<len;i++) {
if(ans<a[i]) {
ans = a[i];
}
}
return ans;
}
}
五结果截图
六总结
这次课堂测试最主要的算法思想是参考的，很多不是自己的思想，主要原因是自己假期里太浪了，学习如逆水行舟不进则退，这次测试给我敲响了警钟，以后一定倍加努力。