这道题也是在黑马论坛上看到的,做了一下,感觉写的过程有点繁琐,大神来看一下,代码哪里还需要改善.
原题:有一串数字字符串array,包含100个正数和负数,并且随机分布,要找到他的一个子串array[i...j](0<=i<=j<=100),使得在array的所有子串中,array[i...j]的元素相加和最大.比如:[1,-2,5,-2,6]的最大子串为[5,-2,6].
代码如下:
- package jishuDemo3;
- import java.util.ArrayList;
- import java.util.Arrays;
- import java.util.HashMap;
- import java.util.Iterator;
- import java.util.Random;
- import java.util.Set;
- public class BaiDuMianShi {
- static int count = 0;
- public static void main(String[] args) {
- Random rd = new Random();
- int[] arr = new int[100];
- ArrayList<Integer> al = new ArrayList<Integer>();
- HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>();
- HashMap<Integer, Integer> hm2 = new HashMap<Integer, Integer>();
- System.out.print("随机到的数组为:[");
- for (int x = 0; x < 10; x++) {
- //arr[x] = rd.nextInt(10);
- arr[x]=(int)(Math.random()*(21)-10);
- if (x != 9) {
- System.out.print(arr[x] + ",");
- } else {
- System.out.println(arr[x] + "]");
- }
- if (arr[x] > 0) {
- al.add(x);
- }
- }
- Iterator<Integer> it = al.iterator();
- while (it.hasNext()) {
- HashMap<Integer, Integer> hm3 = new HashMap<Integer, Integer>();//获取最大值和结束处索引
- int[] reArr = new int[al.size()];//存序列结果集
- int i = it.next();
- for (int x = 0 + count; x < al.size(); x++) {
- int result = getSum(arr, i, al.get(x));//获得相加结果
- reArr[x] = result;//把结果放到数组中
- hm3.put(result, al.get(x));//把结果和正数最大索引放到hm3map中
- }
- Arrays.sort(reArr);//进行排序
- hm.put(reArr[al.size() - 1], i);
- hm2.put(i, hm3.get(reArr[al.size() - 1]));
- hm3.clear();
- count++;
- }
- Set<Integer> c = hm.keySet();
- Integer[] in = c.toArray(new Integer[0]);
- Arrays.sort(in);
- int start = hm.get(in[in.length - 1]);
- int end = hm2.get(start);
- System.out.print("最大子串为:[");
- for (int x = start; x <= end; x++) {
- if (x == end) {
- System.out.print(arr[x] + "]");
- } else {
- System.out.print(arr[x] + ",");
- }
- }
- System.out.println("最大子串和为:" + in[in.length - 1]);
- }
- public static int getSum(int[] arr, int start, int end) {
- int sum = 0;
- for (int x = start; x <= end; x++) {
- sum += arr[x];
- }
- return sum;
- }
- }
复制代码
运行结果:
随机到的数组为:[10,-7,-6,0,8,8,6,-8,7,8]
最大子串为:[8,8,6,-8,7,8]最大子串和为:29
(为了方便输出,我取的的-10到10的10个随机数)
|