找一个数组的最大和的连续子数组(时间复杂度 O(n))(二)

要求:

  要求数组从文件读取。
  如果输入的数组很大,  并且有很多大的数字,  就会产生比较大的结果 (考虑一下数的溢出), 请保证你的程序能正常输出。
  另外, 如果输入文件的参数有错误, 这个程序应该能正常退出, 并显示相应的错误信息。 任何输入错误都不能导致你的程序崩溃。

解决方法及步骤:

  1,先写入一个txt文件,再读取出来

  2,通过循环测试生成的最大容量的数。

  3,写入文件时控制数字的大小,就不会产生大数情况。

  4,再加上上次的代码,计算最大连续子数组的和

  

代码:

  这是随机生成一定量的数并且写入文件

package pri.xcl.test0314;

import java.io.BufferedWriter;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintStream;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.util.Random; public class addtxt { public static void main(String[] args) {
//文件写入
try {
int a= Integer.MAX_VALUE;
int b= Integer.MIN_VALUE;
System.out.println(a);
System.out.println(b);
BufferedWriter out = new BufferedWriter(new FileWriter("1.txt"));
//随机写入100个数
for(int i=0;i<30000000;i++) {
// int x=(int) (Math.random()*10);
int smallistNum=-1000;
int BiggestNum=1000; int x=getRandomNum(smallistNum, BiggestNum);
out.write(x+"\r\n");
}
out.close();
System.out.println("文件创建成功!");
} catch (IOException e) {
} } // 获得一个给定范围的随机整数
public static int getRandomNum(int smallistNum, int BiggestNum) {
Random random = new Random();
return (Math.abs(random.nextInt()) % (BiggestNum - smallistNum + 1))+ smallistNum;
}
}

  读取文件和求最大字数组之和

package pri.xcl.test0314;

import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList; public class test {
public static int[] StringToInt(String[] arrs){ int[] ints = new int[arrs.length]; for(int i=0;i<arrs.length;i++){ ints[i] = Integer.parseInt(arrs[i]); } return ints; } public static void main(String[] args) throws IOException {
//按数组读取文件
ArrayList<String> array;
String line;
int length;
try {
BufferedReader br=new BufferedReader(new FileReader("1.txt"));
array=new ArrayList<String>();
line="";
//按行读取文本中数据
while((line=br.readLine())!=null){
array.add(line);
}
br.close(); length=array.size();
String[] a1 = (String[])array.toArray(new String[length]);
int[] a=StringToInt(a1); // for(int i=0;i<a.length;i++) {
// System.out.println(a[i]);
// }
// int a[]=new int[length];
//
// //遍历输出数组内容
// for(int i=0;i<length;i++) {
// String s=array.get(i);
// a[i]=Integer.parseInt(s);
// System.out.println(a[i]);
// } //进行最大值计算 int sum=0;
int curr=0; //有负有正
for(int i=0;i<length;i++) {
curr=curr+a[i];
if(curr<0) {
curr=0;
}else {
if(sum<curr) {
sum=curr;
}else {
sum=sum;
}
}
} //若全是是负数
if(sum==0) {
int sum1=a[0];
for(int i=0;i<length-1;i++) {
if(sum1>a[i+1]) {
sum1=sum1;
}
else {
sum1=a[i+1];
}
}
sum=sum1;
} System.out.println("连续子数组的最大值为:"+sum); } catch (FileNotFoundException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
}

运行结果

可以生成2000万的数。

找一个数组的最大和的连续子数组(时间复杂度 O(n))(二)

找一个数组的最大和的连续子数组(时间复杂度 O(n))(二)

上一篇:mysql union和union all


下一篇:hdu 1588 求f(b) +f(k+b) +f(2k+b) +f((n-1)k +b) 之和 (矩阵快速幂)