java一维数组作业
2024-09-29 06:26:04
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;
} }
实验截图:
最新文章
- Hibernate的ORM原理和实现
- 如何查看Linux操作系统版本
- java获取本月开始时间和结束时间、上个月第一天和最后一天的时间以及当前日期往前推一周、一个月
- C# Post方式传输报文,和处理响应
- 关于ios项目沙盒中的文件和Xcode项目创建的文件
- JPA主键策略
- 掌握C++基础
- HDU -1284钱币兑换
- HDU 1166 敌兵布阵(树状数组)
- webstorm 2018.1 激活码 2018.4.8日更新
- 【Android Studio安装部署系列】九、Android Studio常用配置以及快捷键
- Linux-网络管理
- 【转载】java abstract class和interface的区别
- Java一次性读取文件的内容
- 引用数据类型(Scanner类、Random类)
- unity3d中gameObject捕获鼠标点击
- 为什么二代测序的原始数据中会出现Read重复现象?
- Ubuntu中安装Flask模块
- 20155335俞昆《java程序设计》第三周总结
- Jboss提示:Server already running on localhost
热门文章
- # 20165225 《Java程序设计》第一周学习总结
- uarts裸机程序
- Linux下Zookeeper的安装
- Spring 注解 @Scheduled(cron = ";0 0/10 * * * ? ";) 动态改变时间
- SVN安装部署
- 为python.exe或者ipython.exe添加环境变量
- IOP知识点(4)
- k8s pv 的三种挂载模式
- Vim的6种基本模式及基本操作
- [pat]1045 Favorite Color Stripe