石家庄铁道大学 信1405-1 班 唐炳辉
题目：给定一个整数数组，找到一个具有最小和的子数组。返回其最小和。
设计思路：两个变量 ，一个记录当前并入的数组的值，另外一个记录所算过得最大的数组的值,当并入的值为小于零的时候，就没必要进行继续的相加了，因为再加也不可能比后边单独的数字大，所以，为负数就重新刷新位置，重置子数组的长度重新去找一个新的子数组
1 //石家庄铁道大学 信1405-1 班 唐炳辉：三藏 2 /**给定一个数组，求出这个数组中子数组的最大值，求出，要求时间复杂度为O(n)**/ 3 package java_ketang; 4 import java.util.Scanner; 5 6 7 8 public class MinArray { 9 10 11 12 public static void main(String[] args) {13MinArray f = new MinArray();14 15//用户自己定义数组的长度并 自行输入一串数组16 17 Scanner in=new Scanner(System.in);18 System.out.print("请输入数组长度：");19 int flase0g=in.nextInt();20 //输入数组中的各个数值21 System.out.print("请依次输入整数：");22 int Arr[]=new int[flase0g];23 for(int i=0;i<flase0g;i++)24 {25 Arr[i]=in.nextInt();26 } 27 //输出用户输入的数组 28 System.out.print("您输入的数组为 ");29 for(int i=0;i<flase0g;i++)30 {31 System.out.print(Arr[i]+" ") ;32 } 33 34 //输出最后的结果35 f.findMaxArr(Arr);36}37 38public void findMaxArr(int[] arr) {39 int Arr = 0;//用来记录当前并入的数组的和40 int MaxArr = 0;//用来记录之前的最大的数组和41 int A = arr.length;42 int Location1=0;43 int Location2=0;//用来记录子数组的最后一个位置44 45 int i;46 47 48/**核心算法，两个变量 ，一个记录当前并入的数组的值，另外一个记录所算过得最大的数组的值49 当并入的值为小于零的时候，就没必要进行继续的相加了，因为再加也不可能比后边单独50 的数字大，所以，为负数就重新刷新位置，重置子数组的长度重新去找一个新的子数组**/51 for ( i = 0; i < A; i++) {52 Arr += arr[i];53 if (Arr < 0) {54 Arr = 0;55 56 57 }58 if (Arr > MaxArr) {59 MaxArr = Arr;60 Location2=i;61 ;62 }63 }64 65 //用这个算法，通过最后的位置，和最大值来求出起始位置66 for(i=Location2;i>=0;i--)67 {68 if(MaxArr-arr[i]==0)69 { 70 Location1=i;//通过求出来的最大值和最后的那个位置，往前推移，找出起始位置71 break;//跳出循环72 }73 74 }75 /**这种情况的出现当且仅当全部的数字都为负数的时候，76对所有的数字求一个最大值就是最大子数组**/77 if (MaxArr == 0) {78 for ( i = 0; i < A; i++) {79 if (i == 0) {80 MaxArr = arr[i];81 }82 if (arr[i] > MaxArr) {83 MaxArr = arr[i];84 }85 }86 }87 //***************88 System.out.println("子数组的长度为"+(Location2-Location1+1));89 System.out.println("子数组是由第 "+(Location1+1)+" 个数到第 "+(Location2+1)+" 个数组成");90 System.out.println("最大子数组的和是 "+MaxArr);91 92}93 }
验证截图
