题目：有一个数字串array,包含100个正数和负数随机分布，要找到他的一个子串array[i...j](0<=i<=j<=100),使得在array的所有子串中，array[i...j]的和最大。比如：串{1,-3,5,-2,6}的最大子串为{5,-2,6}。
import java.util.Arrays;
import java.util.Comparator;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Random;
import java.util.TreeMap;
public class Test4 {
public static void main(String[] args) {
TreeMap<Integer, String> tm = new TreeMap<Integer, String>(new Comparator<Integer>() { //创建TreeMap集合，传入比较器排序
@Override
public int compare(Integer i1, Integer i2) {
int num = i2 - i1;
return num == 0? 1 : num;
}
});
//示例开始--------------------------------------------------------------------
int[] arr = {1,-3,5,-2,6};
System.out.println("示例数组1：");
for (int i : arr) {
System.out.print(i + " ");
}
System.out.println("");
getMax(arr,tm); //获取最大子串
print(arr, tm); //打印最大子串
System.out.println("-----------------------");
int[] arr1 = {1,2,3,4,5,6};
System.out.println("示例数组2：");
for (int i : arr1) {
System.out.print(i + " ");
}
System.out.println();
getMax(arr1,tm); //获取最大子串
print(arr1, tm); //打印最大子串
System.out.println("-----------------------");
//示例结束---------------------------------------------------------------------
//正式开始---------------------------------------------------------------------
int[] arr2 = getRandom(); //获取随机数组
getMax(arr2,tm); //获取最大子串
print(arr2, tm); //打印最大子串
System.out.println("------------------------");
int[] arr3 = getRandom(); //获取随机数组
getMax(arr3,tm); //获取最大子串
print(arr3, tm); //打印最大子串
//运行结束---------------------------------------------------------------------
}
//以上是主方法----------------------------------------------------------------------------------------------------------------------------
public static void print(int[] arr1, TreeMap<Integer, String> tm) { //将源数组和存有其子串的集合传入，打印最大子串
Entry<Integer, String> en = tm.firstEntry(); //获取最大键对应的键值对对象
String s = en.getValue(); //获取最大键
String[] arr = s.split(","); //切割分离出子串长度len和起始位置from
int len = Integer.parseInt(arr[0]); //将分离出的字符串转换成int数
int from = Integer.parseInt(arr[1]);
int[] intArr = Arrays.copyOfRange(arr1, from, from + len); //根据len和from，从源数组中截取最大子串
System.out.print("最大子串是：\n");
for (int i = 0;i < intArr.length; i++) { //打印子串中各元素
System.out.print(intArr + " ");
if (i == 32 || i == 65) { //输出太长就换行
System.out.println("");
}
}
System.out.println(); //换行
}
public static void getMax(int[] arr, Map<Integer, String> map) { //传入源数组和集合，获取数组的各个子串
for (int i = 1; i <= arr.length; i++) { //外层循环定义i为子串长度
for (int j = 0; j <= arr.length - i; j++) { //内层循环定义j为子串起始位置
int[] arr1 = Arrays.copyOfRange(arr, j, i + j); //从源数组中截取的子串arr1
int sum = add(arr1); //调用数组求和方法，对子串中的各元素求和
map.put(sum, (i + "," + j)); //将sum作为键，i和j组合成字符串作为值，存入TreeMap集合中
}
}
}
public static int[] getRandom() { //取得随机源数组
System.out.println("得到的随机数组为：");
int[] arr = new int[100]; //创建长度为100的数组
Random r = new Random(); //创建Random类对象
for (int i = 0; i < arr.length; i++) {
int num = r.nextInt(200) - 100; //获得-100~100之间的随机数
arr = num; //将获得的随机数存入数组
System.out.print(num + " "); //打印每个存入数组的元素
if (i == 32 || i == 65) { //控制台换行(100个数太长，分隔成3行，方便显示)
System.out.println("");
}
}
System.out.println();
return arr;
}
public static int add(int... arr) { //数组求和方法
int sum = 0;
for (int i : arr) {
sum += i;
}
return sum;
}
}
|
|
收藏
淘帖
踩
