黑马程序员技术交流社区

标题: 阳哥32期答案分享，纯手工制作，求喷 [打印本页]

---

作者: blueblueblue    时间: 2016-9-11 13:13
标题: 阳哥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;
        }
}

---

作者: yuanxianzhi    时间: 2016-9-11 14:29
练习下

[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);

                }

                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 + ",");

                        } else

                                System.out.println(arr + "]");

                }

        }

---

作者: ZZqiang    时间: 2016-9-11 14:32
不错，思路挺清晰的

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2