package ch03;
//动态规划归并方法
import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Random;
public class three {
public static File file = new File("D:\\input.txt");
// 创建文件
public static void createData() {
try {
if (!file.exists()) {
file.createNewFile();
}
} catch (Exception e) {
e.printStackTrace();
System.out.println("创建文件操作失败");
}
}
// 写入数据
public static void writeData() {
try {
FileWriter fWriter = new FileWriter("D:\\input.txt");
Random rand = new Random();
for (int i = 0; i < 1000; i++) {
int a = rand.nextInt(2001) - 1000;
fWriter.write("" + a + "\n");
}
fWriter.close();
} catch (Exception e) {
e.printStackTrace();
}
}
// 读取文件
public static int[] readData() {
int[] a = new int[100000];
int i = 0;
try {
InputStreamReader inputStreamReader = new InputStreamReader(new FileInputStream(file));
BufferedReader bReader = new BufferedReader(inputStreamReader);
String line = "";
while (line != null) {
line = bReader.readLine();
if (line != null) {
a[i] = Integer.parseInt(line.trim());//trim()函数是去掉数据的前后空格
i++;
}
}
bReader.close();
inputStreamReader.close();
} catch (Exception e) {
e.printStackTrace();
}
return a;
}
public static int[] getMaxConArray(int left, int right, int[] arr) {
int mid = (left + right) / 2;
if (left == right) {
return new int[] { left, right, arr[left] };
}
int[] leftMaxValue = new int[2];
int[] rightMaxValue = new int[2];
int[] midMaxValue = new int[2];
leftMaxValue = getMaxConArray(left, mid, arr);
rightMaxValue = getMaxConArray(mid + 1, right, arr);
midMaxValue = getMidConArray(left, right, mid, arr);
if (leftMaxValue[2] > rightMaxValue[2] && leftMaxValue[2] > midMaxValue[2]) {
return leftMaxValue;
} else {
if (rightMaxValue[2] > midMaxValue[2]) {
return rightMaxValue;
} else {
return midMaxValue;
}
}
}
private static int[] getMidConArray(int left, int right, int mid, int[] arr) {
int leftMaxValue = 0;
int leftMaxId = mid;
int leftSum = 0;
int rightMaxValue = 0;
int rightMaxId = mid;
int rightSum = 0;
for (int i = 1; i < mid - left + 1; i++) {
leftSum += arr[mid - i];
if (leftMaxValue < leftSum) {
leftMaxValue = leftSum;
leftMaxId = mid - i;
}
}
for (int i = 1; i < right - mid + 1; i++) {
rightSum += arr[mid + i];
if (rightMaxValue < rightSum) {
rightMaxValue = rightSum;
rightMaxId = mid + i;
}
}
return new int[] { leftMaxId, rightMaxId, leftMaxValue + rightMaxValue + arr[mid] };
}
public static void main(String[] args) throws IOException {
createData();
writeData();
int[] A = readData();
int[] B = getMaxConArray(0, A.length - 1, A);
for (int i = B[0]; i < B[1]; i++) {
System.out.print(A[i] + " ");
}
File file1 = new File("D:\\result.txt");
FileWriter out1 = new FileWriter(file1);
out1.write("初始下标是" + B[0] +"\t结束下标是"+ B[1] + "\t最大值" + B[2]);
out1.close();
System.out.println();
System.out.println(B[0]);
System.out.println(B[1]);
System.out.println("最大值为:" + B[2]);
}
}
