任务解释：
一个整数数组中的元素有正有负，在该数组中找出一个连续子数组，要求该连续子数组中各元素的和最大，这个连续子数组便被称作最大连续子数组。
代码在最下方
要求：
随机产生1000以上的数据（有正有负），写入文件input.txt，求出其最大连续子数组
示例：
比如数组{2,4,-7,5,2,-1,2,-4,3}的最大连续子数组为{5,2,-1,2}，最大连续子数组的和为5+2-1+2=8。将结果输出到文件output.txt，并将最大子数组起始元素的索引和结束元素的索引输出到out.txt
原理解释：
首先生成一个包含16个元素的数组
然后我们讲解一下最大子数组问题的主要思路
进行子数组划分的关键代码如下：
findMaximumSubarray(arr, low, mid)
findMaximumSubarray(arr, mid + 1, high)
findMaxCrossingSubarray(arr, low, mid, high)
其中，向左向右寻找左右最大子数组的本质就是分割数组，如下图
findMaximumSubarray(arr, low, mid)//向左寻找最大子数组
findMaximumSubarray(arr, mid + 1, high)//向右寻找最大子数组
而跨越中间值寻找最大子数组才是算法的核心，主要任务是寻找从mid向左右两端出发，分别寻找最大值，并将两者最大值相加
我们以上图中给出的数组为例
第一步：将原数组分成两个子数组
第二步：将两个子数组再分别拆分为四个子数组
左子数组：
右子数组：略
第三步：再次细分
当拆分到第三步问题就变得简单了
int[] leftMax = findMaximumSubarray(arr, low, mid);
int[] rightMax = findMaximumSubarray(arr, mid + 1, high);
int[] crossMax = findMaxCrossingSubarray(arr, low, mid, high);
if (leftMax[2] >= rightMax[2] && leftMax[2] >= crossMax[2]) {
return leftMax;
} else if (rightMax[2] >= leftMax[2] && rightMax[2] >= crossMax[2]) {
return rightMax;
} else {
return crossMax;
}
我们根据代码观察下图，rightMax=19; leftMax=470,而crossMax=489
所以返回crossMax到上一层，以此类推直到返回到数组为初始数组的时候，再比较初始数组的leftMax，rightMax，crossMax
程序运行结果是
（建议不理解的小猿们可以手动分解一下过程，或者私聊小白）
代码
package exam;
import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class MaximumSubarray {
static Integer minValue=Integer.MIN_VALUE;
static List<Integer> list1=new ArrayList<>();//接收生成的数组
/**
* 主方法
* @param args
* @throws IOException
*/
public static void main(String[] args) throws IOException {
Scanner scanner = new Scanner(System.in);
System.out.print("请输入随机生成规模为n的数组，n=");
int n = scanner.nextInt();
Write(n);
int[] a=new int[10];
a=MaximumSubarray.Read(n);
int[] result=findMaximumSubarray(a,0,a.length-1);
int begin=result[0];//最大子数组的起始索引
int end=result[1];//最大子数组的结束索引
int max_SUM=result[2];//最大子数组的和
List<Integer> list2=new ArrayList<>();//list2接收最大子数组
System.out.println("开始的索引"+begin);
System.out.println("结束的索引"+end);
try{
int[] res=new int[end-begin+1];
int k=0;
for (int i = begin; i <=end; i++) {
System.out.println(a[i]);
res[k]=a[i];
k++;
list2.add(a[i]);
}
System.out.println("最大子数组的和为："+max_SUM);
//将要求的参数全部拼接到字符串
String s="数组的a"+list1.toString()+"的最大子数组为"+list2.toString()+"\n最大子数组开始的位置是"+String.valueOf(begin)+"\t结束的位置是"+String.valueOf(end)
+"最大子数组的和为"+String.valueOf(max_SUM);
Write(s);
}catch(Exception e){
System.out.println(e.getMessage());
}
}
/**
* 将拼接成的字符串写入到out.txt
* @param s
* @throws IOException
*/
private static void Write(String s) throws IOException {
File file=new File("D:\\output.txt");
FileWriter out = new FileWriter(file);
out.write(s);
out.close();
}
/**
* 随机生成-1000到1000的数组并写入txt文件
* @param n
* @throws IOException
*/
public static void Write(int n) throws IOException{
int num;
int[] a=new int[n];
//循环生成随机数，存到数组a中
for(int i=0;i<a.length;i++){
num=(int) (Math.random()*(Math.random()>0.5?1:-1)*1000);
a[i]=num;
}
File file=new File("D:\\input.txt");
FileWriter out = new FileWriter(file);
//循环将数组写入文件
for(int i=0;i<a.length;i++){
out.write(a[i]+"\t");
}
out.close();
}
/**
* 跨越中间值寻找最大子数组
* @param arr
* @param low
* @param mid
* @param high
* @return
*/
public static int[] findMaxCrossingSubarray(int[] arr, int low, int mid, int high) {
int leftSum = minValue;
int sum = minValue;
int maxLeft = mid;
for (int i = mid; i >= low; i--) {
sum += arr[i];
if (sum > leftSum) {
maxLeft = i;
leftSum = sum;
}
}
int rightSum = minValue;
sum = minValue;
int maxRight = mid + 1;
for (int i = mid + 1; i <= high; i++) {
sum += arr[i];
if (sum > rightSum) {
maxRight = i;
rightSum = sum;
}
}
return new int[] { maxLeft, maxRight, leftSum + rightSum };
}
/**
* 递归找到最大子数组
* @param array
* @param low
* @param high
* @return
*/
public static int[] findMaximumSubarray(int[] arr, int low, int high) {
if (low == high)
return new int[] { low, high, arr[low] };
int mid=(low + high)/2;
int[] leftMax = findMaximumSubarray(arr, low, mid);
int[] rightMax = findMaximumSubarray(arr, mid + 1, high);
int[] crossMax = findMaxCrossingSubarray(arr, low, mid, high);
if (leftMax[2] >= rightMax[2] && leftMax[2] >= crossMax[2]) {
return leftMax;
} else if (rightMax[2] >= leftMax[2] && rightMax[2] >= crossMax[2]) {
return rightMax;
} else {
return crossMax;
}
}
/**
* @param file
* @param len
* */
public static int[] read(File file, int len) {
InputStreamReader reader = null;
BufferedReader br = null;
try {
reader = new InputStreamReader(new FileInputStream(file));
br = new BufferedReader(reader);
} catch (FileNotFoundException e1) {
e1.printStackTrace();
}
int[] array = new int[len];
String line = "";
try {
int i = 0 ;
while (line != null&&i<len) {
String num = line.trim();
if (num == ""|| num == null){
line = br.readLine();
continue;
}
int a = Integer.parseInt(num);
array[i++] = a;
line = br.readLine();
}
} catch (IOException e) {
e.printStackTrace();
}
return array;
}
/**
* 插入排序，升序
* 升序排序
* @param A
*/
public static void InsertSortAscending(int[] A){
System.out.println(A.length);
for(int j = 1;j < A.length;j++){
int key = A[j];
//将A[j]插入排序序列A[1..j-1]
int i = j - 1;
while(i >= 0 && A[i] > key){
A[i+1] = A[i];
i = i - 1;
}
A[i+1] = key;
}
}
/**
* 读取指定文件中的数组
* @param n
* @return
* @throws IOException
*/
public static int[] Read(int n) throws IOException{
int[] b=new int[n];
File file=new File("D:\\input.txt");
BufferedReader in=new BufferedReader(new FileReader(file));
String line=in.readLine();
String[] temp=line.split("\t");
for(int j=0;j<temp.length;j++){
b[j]=Integer.parseInt(temp[j]);
list1.add(b[j]);
}
in.close();
return b;
}
}