[论坛提问] 今天三个多小时写的一道百度公司的面试题,有没有大神有更简便的方法?

Deathfish

这道题也是在黑马论坛上看到的,做了一下,感觉写的过程有点繁琐,大神来看一下,代码哪里还需要改善.
原题:有一串数字字符串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个随机数)

半月 · 半月

public class baidu {
public static void main(String[] args) {
String[] num = getArray(10);
System.out.println(Arrays.toString(num));
maxSubNum(num);
}
public static void maxSubNum(String[] str){
//最大和值
int max = Integer.parseInt(str[0]);
//最大和值的开始和结束位置
int overStart = 0,overEnd = 0;
for (int i = 0; i < str.length; i++) {
for (int start = 0,end = start + i; end < str.length;start++,end++) {
int temp = sumStr(str,start,end);
if(max<temp){
max = temp;
overStart = start;
overEnd = end;
}
}
}
System.out.println("max = " + max);
SubStr(str,overStart,overEnd);
}
//输出i-j的子字符串
public static void SubStr(String[] str,int start,int end){
for (int i = start; i <= end; i++) {
System.out.print(str[i]+" ,");
}
System.out.println();
}
//计算数组i-j之间和值
public static int sumStr(String[] str,int i,int j){
int sum = 0;
for (int x = i; x <= j; x++) {
sum += Integer.parseInt(str[x]);
}
return sum;
}
//生成数组
public static String[] getArray(int num){
Random r =new Random();
String[] numStr = new String[num];
for (int i = 0; i < num; i++) {
numStr[i] = (r.nextInt(num<<1)-num)+"";
}
return numStr;
}
}

复制代码

java8023 · java8023

都没看懂题目意思

as604049322 · as604049322

又是半年前我做过的最大子列和问题

as604049322 · as604049322

用“在线处理”和“分而治之”的思想求“最大子列和”...
http://bbs.itheima.com/thread-157150-1-1.html
(出处: 黑马程序员IT技术论坛)

ETOLIA · ETOLIA

as604049322 发表于 2015-6-9 19:06
用“在线处理”和“分而治之”的思想求“最大子列和”...
http://bbs.itheima.com/thread-157150-1-1.html
...

这个办法不错。。赞

zuoyou · zuoyou

研究研究，，，，

天涯111 · 天涯111

看着题目都感觉好难不过又学到新东西哎大神到处都是啊！！！赶快学习

Deathfish · Deathfish

本帖最后由 Deathfish 于 2015-6-9 21:59 编辑

这个是课本上的题目
下面是时间复杂度O(N)的代码。

public static int crazyMaxSubList(int [] a)
{
int thisSum = 0;
int maxSum = 0;
int indexTemp = 0 , indexMax = 0;
int sizeTemp = 0, sizeMax;
for (int i = 0; i < a.length; i++)
{
thisSum += a[i];
if (thisSum > maxSum)
{
maxSum = thisSum;
indexMax = indexTemp;
sizeMax = sizeTemp;
}
else if (thisSum < 0)
{
thisSum = 0;
indexTemp = i;
sizeTemp = 0;
}
else
{
sumTemp = maxSum;
sizeTemp++;
}
}
System.out.println("max sub index for :" + indexMax + " size is "+ sizeMax);
return maxSum;

复制代码

bingyu · bingyu

自己写的对题意理解的不是很明白

package com.cn.beijing;
public class Demo {
public static void main(String[] args) {
// TODO Auto-generated method stub
int arr[] = { 10, -7, -6, 0, 8, 8, 6, -8, 7, 8 };
int temp = arr[0];
int astart = 0;
int aend = 0;
for (int i = 0; i <= arr.length; i++) {
for (int start = 0, end = i; end < arr.length; start++, end++) {
int sum = 0;
System.out.println("start...end..."+start+"..."+end);
for (int j = start; j <= end; j++) {
sum += arr[j];
System.out.println("sum="+sum);
}
if (sum >= temp) {
temp = sum;
astart = start;
aend = end;
}
}
}
System.out.println(astart + "...." + aend + "...." + temp);
}
}

复制代码

micro_hx · micro_hx

package com.test1;
/**
* 计算最大子列问题
*/
public class Test1 {
public static void main(String[] args) {
int arr[] = {2,-4,5,2,-54,-45,3,-5,8,-4} ;
int temp = 0 ;
int max = 0 ;
for(int i = 0 ; i < arr.length ; i++){
temp += arr[i];
//因为数组中至少存在正数，故最大值不可能为非正数
if(temp < 0){
temp = 0 ;
}
//一旦大于0，需要拿过来比较
if(temp > max){
max = temp ;
}
}
//单个字符可能为最大值，故所以这里需判断一下
if(max == 0){
for (int i = 0; i < arr.length; i++) {
if(arr[i] > max)
max = arr[i];
}
}
System.out.println(max +"====" + temp);
}
}

复制代码

看看我的，应该很简单的，希望对你有作用。。。。

海角秋风 · 海角秋风

好好学习一下。。。

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

[论坛提问] 今天三个多小时写的一道百度公司的面试题,有没有大神有更简便的方法?

评分

11 个回复

优秀作者