首页 > 代码库 > java一维数组作业
java一维数组作业
package zuoYe; import java.util.Scanner; public class MaxSubArray { public static void main(String[] args) { Scanner scan = new Scanner(System.in); //输入数据 System.out.println("请输入数组长度"); int n = scan.nextInt(); int[] a = new int[n]; System.out.println("请输入数组元素"); for(int i = 0;i < n;i++) { a[i] = scan.nextInt(); } scan.close(); //计算此数组的和最大的连续子数组 int[] result = maxSub(a,a.length); System.out.println("不连接成环的和最大的连续子数组:"); for(int i = result[0];i <= result[1];i++) { System.out.print(a[i] + "\t"); } System.out.println("和为:" + result[2]); //将此数组连成一个环,再计算此数组的和最大的连续子数组 //连成一个环即将数组后再接上此数组,但是数组的最后一个元素不用接,相当于计算接上之后的数组的和最大子数组 int[] b = new int[2 * n - 1]; for(int i = 0;i < n - 1;i++) { b[i] = a[i]; b[n + i] = a[i]; } b[n - 1] = a[n - 1]; int[] result2 = maxSub(b,n); System.out.println("\n\n将数组连成环后的和最大的连续子数组:"); for(int i = result2[0];i <= result2[1];i++) { System.out.print(b[i] + "\t"); } System.out.println("和为:" + result2[2]); } //计算a数组的和最大的连续子数组(a数组为连成环后的等价数组,即原数组的二倍,n为原数组的长度) public static int[] maxSub(int[] a,int n) { int an = a.length;//连成环的等价数组的长度 int currectSum = a[0];//记录当前累加和,初始值为a[0] int currectStartIndex = 0;//记录当前累加的起始下标,初始值为0 int count = 1;//记录累加元素的个数,初始值为1 int[] result = new int[3];//记录结果子数组的信息, result[0] = 0;//结果子数组的开始下标 result[1] = 0;//结果子数组的结束下标 result[2] = a[0];//结果子数组的和 for(int i = 1;i < an;i++)//依次遍历a数组的每个元素 { if(currectSum <= 0)//如果当前累加和不大于0,不大于0对后续的元素没有贡献,可以去掉了,所以应从a[i]处重新开始加 { currectSum = a[i];//将当前累加和赋值为a[i] currectStartIndex = i;//将当前累加的开始下标赋值为i count = 1;//将累加元素的个数记为1 } else//当前累加和大于0,则继续加a[i] { currectSum += a[i]; count++;//当前累加元素的个数加一 } if(currectSum > result[2])//如果当前累加和大于原结果数组的累加和result[2],则应该将结果子数组信息更新为当前子数组,因为当前子数组的累加和大于结果子数组的和 { result[0] = currectStartIndex;//结果子数组的开始下标为当前子数组的开始下标 result[1] = i;//结果子数组的结束下标赋值为i result[2] = currectSum;//结果子数组的累加和赋值为当前子数组的累加和 } if(count >= n)//如果累加的元素个数等于原数组(未连成环的数组)的长度,则说明已经加了最多的元素,不能再加了,也就是说和最大的子数组即为原数组,应该结束循环 { break; } } return result; } }
实验截图:
java一维数组作业
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。