A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

这道题也是在黑马论坛上看到的,做了一下,感觉写的过程有点繁琐,大神来看一下,代码哪里还需要改善.
原题:有一串数字字符串array,包含100个正数和负数,并且随机分布,要找到他的一个子串array[i...j](0<=i<=j<=100),使得在array的所有子串中,array[i...j]的元素相加和最大.比如:[1,-2,5,-2,6]的最大子串为[5,-2,6].
代码如下:
  1. package jishuDemo3;

  2. import java.util.ArrayList;
  3. import java.util.Arrays;
  4. import java.util.HashMap;
  5. import java.util.Iterator;
  6. import java.util.Random;
  7. import java.util.Set;

  8. public class BaiDuMianShi {
  9.         static int count = 0;

  10.         public static void main(String[] args) {
  11.                 Random rd = new Random();
  12.                 int[] arr = new int[100];
  13.                 ArrayList<Integer> al = new ArrayList<Integer>();
  14.                 HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>();
  15.                 HashMap<Integer, Integer> hm2 = new HashMap<Integer, Integer>();
  16.                 System.out.print("随机到的数组为:[");
  17.                 for (int x = 0; x < 10; x++) {
  18.                         //arr[x] = rd.nextInt(10);
  19.                         arr[x]=(int)(Math.random()*(21)-10);
  20.                         if (x != 9) {
  21.                                 System.out.print(arr[x] + ",");
  22.                         } else {
  23.                                 System.out.println(arr[x] + "]");
  24.                         }
  25.                         if (arr[x] > 0) {
  26.                                 al.add(x);
  27.                         }
  28.                 }
  29.                 Iterator<Integer> it = al.iterator();
  30.                 while (it.hasNext()) {
  31.                         HashMap<Integer, Integer> hm3 = new HashMap<Integer, Integer>();//获取最大值和结束处索引
  32.                         int[] reArr = new int[al.size()];//存序列结果集
  33.                         int i = it.next();
  34.                         for (int x = 0 + count; x < al.size(); x++) {
  35.                                 int result = getSum(arr, i, al.get(x));//获得相加结果
  36.                                 reArr[x] = result;//把结果放到数组中
  37.                                 hm3.put(result, al.get(x));//把结果和正数最大索引放到hm3map中
  38.                         }
  39.                         Arrays.sort(reArr);//进行排序
  40.                         hm.put(reArr[al.size() - 1], i);
  41.                         hm2.put(i, hm3.get(reArr[al.size() - 1]));
  42.                         hm3.clear();
  43.                         count++;
  44.                 }
  45.                 Set<Integer> c = hm.keySet();
  46.                 Integer[] in = c.toArray(new Integer[0]);
  47.                 Arrays.sort(in);
  48.                 int start = hm.get(in[in.length - 1]);
  49.                 int end = hm2.get(start);
  50.                 System.out.print("最大子串为:[");
  51.                 for (int x = start; x <= end; x++) {
  52.                         if (x == end) {
  53.                                 System.out.print(arr[x] + "]");
  54.                         } else {
  55.                                 System.out.print(arr[x] + ",");
  56.                         }
  57.                 }
  58.                 System.out.println("最大子串和为:" + in[in.length - 1]);

  59.         }

  60.         public static int getSum(int[] arr, int start, int end) {
  61.                 int sum = 0;
  62.                 for (int x = start; x <= end; x++) {
  63.                         sum += arr[x];
  64.                 }
  65.                 return sum;
  66.         }
  67. }
复制代码


运行结果:
随机到的数组为:[10,-7,-6,0,8,8,6,-8,7,8]
最大子串为:[8,8,6,-8,7,8]最大子串和为:29
(为了方便输出,我取的的-10到10的10个随机数)

评分

参与人数 1黑马币 +17 收起 理由
Deathfish + 17 淡定

查看全部评分

11 个回复

倒序浏览
  1. public class baidu {
  2.         public static void main(String[] args) {
  3.                 String[] num = getArray(10);
  4.                 System.out.println(Arrays.toString(num));
  5.                 maxSubNum(num);
  6.         }
  7.        
  8.         public static void maxSubNum(String[] str){
  9.                 //最大和值
  10.                 int max = Integer.parseInt(str[0]);
  11.                 //最大和值的开始和结束位置
  12.                 int overStart = 0,overEnd = 0;
  13.                 for (int i = 0; i < str.length; i++) {
  14.                         for (int start = 0,end = start + i; end < str.length;start++,end++) {
  15.                                 int temp = sumStr(str,start,end);
  16.                                 if(max<temp){
  17.                                         max = temp;
  18.                                         overStart = start;
  19.                                         overEnd = end;
  20.                                 }
  21.                         }
  22.                 }
  23.                 System.out.println("max = " + max);
  24.                 SubStr(str,overStart,overEnd);
  25.         }
  26.        
  27.         //输出i-j的子字符串
  28.         public static void SubStr(String[] str,int start,int end){
  29.                 for (int i = start; i <= end; i++) {
  30.                         System.out.print(str[i]+" ,");
  31.                 }
  32.                 System.out.println();
  33.         }
  34.        
  35.         //计算数组i-j之间和值
  36.         public static int sumStr(String[] str,int i,int j){
  37.                 int sum = 0;
  38.                 for (int x = i; x <= j; x++) {
  39.                         sum += Integer.parseInt(str[x]);
  40.                 }
  41.                 return sum;
  42.         }
  43.        
  44.         //生成数组
  45.         public static String[] getArray(int num){
  46.                 Random r =new Random();
  47.                 String[] numStr = new String[num];
  48.                 for (int i = 0; i < num; i++) {
  49.                         numStr[i] = (r.nextInt(num<<1)-num)+"";
  50.                 }
  51.                 return numStr;
  52.         }
  53. }
复制代码
回复 使用道具 举报
都没看懂题目意思
回复 使用道具 举报
又是半年前我做过的最大子列和问题
回复 使用道具 举报
用“在线处理”和“分而治之”的思想求“最大子列和”...
http://bbs.itheima.com/thread-157150-1-1.html
(出处: 黑马程序员IT技术论坛)
回复 使用道具 举报
as604049322 发表于 2015-6-9 19:06
用“在线处理”和“分而治之”的思想求“最大子列和”...
http://bbs.itheima.com/thread-157150-1-1.html
...

这个办法不错。。赞
回复 使用道具 举报
研究研究,,,,
回复 使用道具 举报
看着题目都感觉好难   不过又学到新东西    哎 大神到处都是啊!!!赶快学习
回复 使用道具 举报
本帖最后由 Deathfish 于 2015-6-9 21:59 编辑

这个是课本上的题目
下面是时间复杂度O(N)的代码。
  1.         public static int crazyMaxSubList(int [] a)
  2.         {
  3.                 int thisSum = 0;
  4.                 int maxSum = 0;
  5.                 int indexTemp = 0 , indexMax = 0;
  6.                 int sizeTemp = 0, sizeMax;
  7.                 for (int i = 0; i < a.length; i++)
  8.                 {
  9.                         thisSum += a[i];

  10.                         if (thisSum > maxSum)
  11.                         {
  12.                                 maxSum = thisSum;
  13.                                 indexMax = indexTemp;
  14.                                 sizeMax = sizeTemp;
  15.                         }        
  16.                         else if (thisSum < 0)
  17.                         {        
  18.                                 thisSum = 0;
  19.                                 indexTemp = i;
  20.                                 sizeTemp = 0;
  21.                         }
  22.                         else
  23.                         {
  24.                                 sumTemp = maxSum;
  25.                                 sizeTemp++;
  26.                         }
  27.                 }
  28.                 System.out.println("max sub index for :" + indexMax + " size is "+ sizeMax);
  29.                 return maxSum;
复制代码



回复 使用道具 举报
自己写的 对题意理解的不是很明白
  1. package com.cn.beijing;

  2. public class Demo {

  3.         public static void main(String[] args) {
  4.                 // TODO Auto-generated method stub
  5.                 int arr[] = { 10, -7, -6, 0, 8, 8, 6, -8, 7, 8 };
  6.                 int temp = arr[0];
  7.                 int astart = 0;
  8.                 int aend = 0;
  9.                 for (int i = 0; i <= arr.length; i++) {

  10.                         for (int start = 0, end = i; end < arr.length; start++, end++) {
  11.                                 int sum = 0;
  12.                                 System.out.println("start...end..."+start+"..."+end);
  13.                                 for (int j = start; j <= end; j++) {
  14.                                         sum += arr[j];
  15.                                         System.out.println("sum="+sum);
  16.                                 }
  17.                                 if (sum >= temp) {
  18.                                         temp = sum;
  19.                                         astart = start;
  20.                                         aend = end;
  21.                                 }
  22.                         }
  23.                 }
  24.                 System.out.println(astart + "...." + aend + "...." + temp);
  25.         }
  26. }
复制代码

回复 使用道具 举报
  1. package com.test1;

  2. /**
  3. * 计算最大子列问题
  4. */
  5. public class Test1 {
  6.         public static void main(String[] args) {
  7.                 int arr[] = {2,-4,5,2,-54,-45,3,-5,8,-4} ;
  8.                
  9.                 int temp = 0 ;
  10.                 int max = 0 ;
  11.                 for(int i = 0 ; i < arr.length ; i++){
  12.                                 temp += arr[i];
  13.                                
  14.                                 //因为数组中至少存在正数,故最大值不可能为非正数
  15.                                 if(temp < 0){
  16.                                         temp = 0 ;
  17.                                 }
  18.                                
  19.                                 //一旦大于0,需要拿过来比较
  20.                                 if(temp > max){
  21.                                         max = temp ;
  22.                                 }
  23.                 }
  24.                
  25.                 //单个字符可能为最大值,故所以这里需判断一下
  26.                 if(max == 0){
  27.                         for (int i = 0; i < arr.length; i++) {
  28.                                         if(arr[i] > max)
  29.                                                 max = arr[i];
  30.                         }
  31.                 }
  32.                
  33.                 System.out.println(max +"====" + temp);
  34.                
  35.         }
  36. }
复制代码


看看我的,应该很简单的,希望对你有作用。。。。
回复 使用道具 举报
好好学习一下。。。
回复 使用道具 举报
您需要登录后才可以回帖 登录 | 加入黑马