[学习交流] 阳哥32期答案分享，纯手工制作，求喷

题目：有一个数字串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;
}
}

ZZqiang · ZZqiang

不错，思路挺清晰的

yuanxianzhi · yuanxianzhi

练习下

[Java] 纯文本查看 复制代码

	public static void main(String[] args) {

		// int array[] = { 233333, -3222, 5, -222227, 11, -224, 66, -23, 45,-66, 123 };
		Integer array[] = getRandom();
		printArray(array);
		//定义变量比较子串大小
		int temp = Integer.MIN_VALUE;
		//子串开始位置
		int start = 0;
		//子串结束位置（包含）
		int end = 0;
		//从0角标开始计算所有子串的和值
		for (int i = 0; i < array.length; i++) {
			for (int j = i; j < array.length; j++) {
				int sum = 0;
				//计算从i角标开始，各个子串的总和
				for (int x = i; x <= j; x++) {
					sum += array[x];
				}
				//保存子串开始结尾
				if (sum > temp) {
					temp = sum;
					start = i;
					end = j;
				}
			}
		}
		System.out.println("开始角标:"+start + " 结束角标:" + end);
		//取出子串并打印
		Integer array_2[] = get(array, start, end);
		System.out.print("最大和子串");
		printArray(array_2);

	}
	//取子串 包含开头包含结尾
	private static Integer[] get(Integer[] array, int start, int end) {
		ArrayList<Integer> list = new ArrayList<>();
		for (int i = start; i <= end; i++) {
			list.add(array[i]);
		}
		Integer in[] = new Integer[list.size()];
		return list.toArray(in);
	}
	//生成随机数组
	public static Integer[] getRandom() {
		Random r = new Random();
		ArrayList<Integer> list = new ArrayList<>();
		for (int i = 0; i < r.nextInt(20) + 5; i++) {
			if (i % 2 == 0) {
				list.add(r.nextInt(200));
			} else
				list.add(-r.nextInt(200));
		}
		Integer[] in = new Integer[list.size()];
		return list.toArray(in);
	}
	//打印数组
	public static void printArray(Integer arr[]) {
		System.out.print("[");
		for (int i = 0; i < arr.length; i++) {
			if (i != arr.length - 1) {
				System.out.print(arr[i] + ",");
			} else
				System.out.println(arr[i] + "]");
		}
	}

帐号		自动登录	找回密码
密码			加入黑马

[学习交流] 阳哥32期答案分享，纯手工制作，求喷

2 个回复