任務解釋：
一個整數數組中的元素有正有負，在該數組中找出一個連續子數組，要求該連續子數組中各元素的和最大，這個連續子數組便被稱作最大連續子數組。
代碼在最下方
要求：
随機産生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;
}
}