1.返回一个数组中最大子数组的和
要求:输入一个整形数组,数组里有正也有负数
数组中连续的一个或多个数组组成一个子数组,每个子数组都有一个和
求所有子数组的和的最大值,要求时间复杂度为O(n)
思路:另设两个数组,一个记录和b[],一个记录当前子数组的个数c[]。如果原数组的第二个数加上第一个数的和小于第二个数,那么舍弃第一个数,当前子数组的个数为一。由此类推,直到遍历完所有数组。
package test;
import java.util.Random;import java.util.Scanner;
public class array_test {
public static void main(String[] args) {
Scanner scanner=new Scanner(System.in);
int[] num=new int[20];
int number=0;
int[] array1=new int[20];
int a=scanner.nextInt();
for(int i=0;i<a;i++) {
//随机生成数组里的数字
array1[i]=scanner.nextInt();
}
num[0]=array1[0];
for (int i = 1; i < array1.length; i++) {
if(array1[i]+array1[i-1]>array1[i]) {
num[i]=num[i-1]+array1[i];
number=i+1;
}
else {
num[i]=array1[i];
}
}
int max=num[0];
for(int i=1;i<num.length;i++) {
System.out.print(num[i]);
if(num[i]>max)
max=num[i];
}
System.out.print(max);
System.out.print(" ");
}
}
2.求一个循环数组中最大子数组的和
要求:在第一问的前提下,将原数组变为循环数组
思路:将原数组循环赋值,直到子数组的个数大于原数组的个数时停止
import java.util.Random;import java.util.Scanner;
public class huan {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int a[]=new int[10000];
int b[]=new int[20000];
int sum,d,temp1=0,temp2=0,flag1=0,flag2=0; //分别记录子数列的起始和结束位置
System.out.print("请输入数组元素的个数: ");
Scanner sc=new Scanner(System.in);
int m=sc.nextInt();
if(m>999999)
{
System.out.print("请重新输入数组元素的个数: ");
m=sc.nextInt();
}
Random rand = new Random();
for(int i=0;i<m;i++)//循环为数组赋值 {
a[i] = rand.nextInt(40)-20;
b[i] = a[i];
b[i+m]=a[i];
System.out.print(a[i]+" ");
}
sum=b[0];
d=sum;
for(int i=0;i<2*m;i++)//核心循环,来判断怎么产生最大子数组 {
if(d<=0){
d=0;
temp1=i+1;
temp2=i;
}
d+=b[i+1];
temp2++;
if(d>sum){
sum=d;
flag1=temp1;
flag2=temp2;
if((flag2-flag1+1)>=m)
{
break;
}
}
}
System.out.println("");
System.out.print("子数组的组成元素为: ");
for(int i=flag1;i<=flag2;i++)
System.out.print(b[i]+" ");
System.out.println("");
System.out.println("子数组和的最大值为: "+sum);
}
}
3.要求数组从文件中读取
要求:数组从文件中读取
如果输入的数组过大,考虑一下数的溢出
保证文件中错误的参数不能导致程序的崩溃
package test;
import java.io.BufferedReader;import java.io.FileNotFoundException;import java.io.FileReader;import java.io.IOException;
public class array_test2 {
public static void main(String[] args) throws IOException {
FileReader fileReader=new FileReader("C:\\Users\\admin\\Desktop\\QQ\\test.txt");
BufferedReader bReader=new BufferedReader(fileReader);
StringBuffer stringBuffer=new StringBuffer();
String[] strings=new String[50];
String bb;
String s="";
while((bb=bReader.readLine())!=null) {
s=s+bb;
}
String [] data=s.split(" ");
int [] datas=new int [data.length];
//将String类型数组转成int类型
for(int j=0;j<data.length;j++)
{
datas[j]=Integer.parseInt(data[j]);
}
for(int i=0;i<datas.length;i++)
{
System.out.print(datas[i]+" ");
}
int[] num=new int[50];
num[0]=datas[0];
int number=0;
for(int i=1;i<datas.length;i++) {
if(datas[i]+datas[i-1]>datas[i]) {
num[i]=datas[i]+num[i-1];
number=number+1;
}
else {
num[i]=datas[i];
}
}
int max=num[0];
for(int i=1;i<datas.length;i++) {
System.out.print(num[i]+" ");
if(num[i]>max)
max=num[i];
}
System.out.print(max+" ");
System.out.print(number);
}
}
标签:int,System,num,数组,new,out From: https://www.cnblogs.com/wass/p/17154410.html