论坛首页 Java企业应用论坛

一个道说难不难,说简单不简单的Java编程题

浏览 16419 次
精华帖 (1) :: 良好帖 (0) :: 新手帖 (2) :: 隐藏帖 (0)
作者 正文
   发表时间:2012-05-04  
如果是最大的子数组和的话,应该就是所有正数的的那个子数组吧
0 请登录后投票
   发表时间:2012-05-04  
hiloo 写道
这种贴也可以上首页?javaEye现在是疯了

看起来简单,但是你看吧,这么多回帖的,还有帖代码的,有几个时间复杂度控制在O(n)了?
所以这个题对广大苦力的教育意义还是比较深远的。
0 请登录后投票
   发表时间:2012-05-04  

很简单嘛,两重循环,给个答案,自己跑了ok

public class ArrayCul {

	public static void main(String args[]){
		int[] array = {-1,-2,-3,4,5,7,8,10,16,19};
		System.out.println(Arrays.toString(arrayCul(array)));
	}
	private static int[] arrayCul(int[] array){
		if(array == null || array.length == 0){
			return null;
		}
		int i = array.length;
		int[] temp = new int[array.length];
		int[] arrayValue;
		long tempSum = Long.MIN_VALUE  ;
		long value;
		for (int j = 0; j < i; j++) {
			for (int k = j+1; k <= i; k++) {
				arrayValue = Arrays.copyOfRange(array, j, k);
				value = arraySum(arrayValue);
				if(value > tempSum){
					tempSum = value;
					temp = arrayValue;
					System.out.println(Arrays.toString(temp));
				}
			}
		}
		return temp;
	}
	private static long arraySum(int[] array){
		long sum = 0;
		if(array == null || array.length == 0){
			return  Long.MIN_VALUE;
		}
		for (int i = 0; i < array.length; i++) {
			sum+=array[i];
		}
		return sum;
	}
}
 
0 请登录后投票
   发表时间:2012-05-05  
public class Test
{

public static void main(String[] args)
{
int arr[]={1,2,0,5,-1,-2,4,8,12};
for (int i = 0; i < arr.length; i++)
{
calc(i + 1, arr);

}


}

private static void calc(int subArrayLength, int[] arr)
{
int newLen = arr.length - subArrayLength;
for(int i = 0; i<= newLen; i++)
{
int[] temp = new int[subArrayLength];
    System.arraycopy(arr, i, temp, 0, subArrayLength);
    System.out.println(Arrays.toString(temp)+ "   =   "+ sum(temp));

}
}

public static int sum(int[] temp)
{
int sum = 0;
for (int i = 0; i < temp.length; i++)
{
sum += temp[i];
}
return sum;
}

}
0 请登录后投票
   发表时间:2012-05-05  
zhangbin505 写道
public class Test
{

public static void main(String[] args)
{
int arr[]={1,2,0,5,-1,-2,4,8,12};
for (int i = 0; i < arr.length; i++)
{
calc(i + 1, arr);

}


}

private static void calc(int subArrayLength, int[] arr)
{
int newLen = arr.length - subArrayLength;
for(int i = 0; i<= newLen; i++)
{
int[] temp = new int[subArrayLength];
    System.arraycopy(arr, i, temp, 0, subArrayLength);
    System.out.println(Arrays.toString(temp)+ "   =   "+ sum(temp));

}
}

public static int sum(int[] temp)
{
int sum = 0;
for (int i = 0; i < temp.length; i++)
{
sum += temp[i];
}
return sum;
}

}



答案:
[1]   =   1
[2]   =   2
[0]   =   0
[5]   =   5
[-1]   =   -1
[-2]   =   -2
[4]   =   4
[8]   =   8
[12]   =   12
[1, 2]   =   3
[2, 0]   =   2
[0, 5]   =   5
[5, -1]   =   4
[-1, -2]   =   -3
[-2, 4]   =   2
[4, 8]   =   12
[8, 12]   =   20
[1, 2, 0]   =   3
[2, 0, 5]   =   7
[0, 5, -1]   =   4
[5, -1, -2]   =   2
[-1, -2, 4]   =   1
[-2, 4, 8]   =   10
[4, 8, 12]   =   24
[1, 2, 0, 5]   =   8
[2, 0, 5, -1]   =   6
[0, 5, -1, -2]   =   2
[5, -1, -2, 4]   =   6
[-1, -2, 4, 8]   =   9
[-2, 4, 8, 12]   =   22
[1, 2, 0, 5, -1]   =   7
[2, 0, 5, -1, -2]   =   4
[0, 5, -1, -2, 4]   =   6
[5, -1, -2, 4, 8]   =   14
[-1, -2, 4, 8, 12]   =   21
[1, 2, 0, 5, -1, -2]   =   5
[2, 0, 5, -1, -2, 4]   =   8
[0, 5, -1, -2, 4, 8]   =   14
[5, -1, -2, 4, 8, 12]   =   26
[1, 2, 0, 5, -1, -2, 4]   =   9
[2, 0, 5, -1, -2, 4, 8]   =   16
[0, 5, -1, -2, 4, 8, 12]   =   26
[1, 2, 0, 5, -1, -2, 4, 8]   =   17
[2, 0, 5, -1, -2, 4, 8, 12]   =   28
[1, 2, 0, 5, -1, -2, 4, 8, 12]   =   29
0 请登录后投票
   发表时间:2012-05-05  
楼主,你这个是要找最大子序列吧?
0 请登录后投票
   发表时间:2012-05-05  
再看了一遍lz的问题,应该就是算法里面的经典问题,求“最大子序列”。。。暂时提供三个算法,时间复杂度嘛应该很容易看出来的,就不分析了哈!这个在一本国外的算法与数据结构的经典书前两章有讲,建议大家多看。书名我记不住了,回去看一下在回。
public static int maxSubSum1(int a[])
{
int maxSum = 0;

for (int i = 0; i < a.length; i++)
{
for (int j = i; j < a.length; j++)
{
int thisSum = 0;

for (int k = i; k <= j; k++)
{
thisSum += a[k];
}

if (thisSum > maxSum)
maxSum = thisSum;
}
}

return maxSum;
}

public static int maxSubSum2(int a[])
{
int maxSum = 0;

for (int i = 0; i < a.length; i++)
{
int thisSum = 0;
for (int j = i; j < a.length; j++)
{
thisSum += a[j];

if (thisSum > maxSum)
maxSum = thisSum;
}
}

return maxSum;
}

public static int maxSubSum3(int a[])
{
int maxSum = 0;
int thisSum = 0;

for (int i = 0; i < a.length; i++)
{
thisSum += a[i];
if (thisSum > maxSum)
{
maxSum = thisSum;
}
else if (thisSum < 0)
{
thisSum = 0;
}
}

return maxSum;
}
0 请登录后投票
   发表时间:2012-05-05  
public class FindMaxSubArray {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[] array = new int[] { -2, 31, -30, 50, 3, -6, 4, -8, 6, 5 };

		findMaxSubArray(array);

	}

	public static int findMaxSubArray(int[] array) {
		int len = array.length;
		int max = array[len - 1]; // max result

		int end = len - 1; // end position
		int end2 = end;
		int start = end; // start position

		int temp = array[len - 1];

		for (int i = len - 2; i > 0; i--) {
			// 如果当前子数组小于零,则最大子数组必定不包含当前子数组
			if (temp < 0) {
				temp = 0;
				end2 = i;
			}
			temp += array[i];

			if (temp > max) {
				max = temp;
				start = i;
				end = end2;
			}
		}
		System.out.println("start at " + start + " end with " + end + ". Max sum is " + max);
		return max;
	}
}
0 请登录后投票
   发表时间:2012-05-05  
我也贴一个测试通过的算法:
基本思路与前面几位朋友是一样的,就是记录一个能使当前连续的值之和最大化的数字,出现负数时,该值停止加和操作;另外记录一个连续的负值之和,当遇到正数时,拿前一个加和与后一个负值的加和进行比较,如果前者大于后者的绝对值,则认为是连接有效的值,将后者追加到前者上去,直至结束;单次遍历即可实现,无须双循环。
(学校的算法已经忘光了,只能靠自己的理解来做了,汗~)
public class Test{
	
	public static void findMax(int[] arr){
		
		 int init = arr[0];
		 int broken = 0;
		 int count = 1;
		 int maxIndex = 0;
		 int breakCount=0;
		 for(int i=1;i<arr.length;i++){
		 	   if(init+arr[i]<init && arr[i] > init){//当前值即为已知的最大值
		 	   	  init = arr[i];
		 	   	  broken = 0;
		  			count = 1;
		 			 	breakCount=0;
		 			 	maxIndex = i;
		 	   	} else if(init+arr[i]<=init ){//当前值为非正数值,即出现搞破坏的值
		 	   		//init = arr[i];
		 	   		broken += arr[i];
		 	   		breakCount++;
		 	   	} else {//出现正数值
		 	   		if(init+arr[i] > -broken) {//可将连续中断的值接入
		 	   		init = init+broken+arr[i];
		 	   		count += breakCount+1;
		 	   		} else {//中断值舍去
		 	   		 init=arr[i];
		 	   		 count=1;
		 	   		 //broken+=arr[i];
		 	   		}
		 	   		 broken = 0;
		 	   		 breakCount = 0;
		 			 	maxIndex = i;
		 	   		}
		 	   		System.out.println("第"+i+"轮循环:arr[i]="+arr[i]+",init="+init+",broken="+broken);
		 	}
		 		System.out.print("输出数组数据:");
		 	for(int i = maxIndex-count+1;i<=maxIndex;i++){
		 		System.out.print(arr[i] + "  ");
		 		}
		 	System.out.println();
		 	System.out.println("the result is:"+init);
		}
	
	public static void main(String[] args){
		 int[] arr = {2,4,0,-1,-2,4,8,12};
		 //int[] arr = {-1,-2,-3};
		 //int[] arr={-1,-2,-3,0,0,1, 1,1,-5,1,1,1,1,1,-2,-1,0,4,-3,0,-1};
		 findMax(arr);
	}
}
0 请登录后投票
   发表时间:2012-05-06  
helloboy077 写道
public class FindMaxSubArray {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[] array = new int[] { -2, 31, -30, 50, 3, -6, 4, -8, 6, 5 };

		findMaxSubArray(array);

	}

	public static int findMaxSubArray(int[] array) {
		int len = array.length;
		int max = array[len - 1]; // max result

		int end = len - 1; // end position
		int end2 = end;
		int start = end; // start position

		int temp = array[len - 1];

		for (int i = len - 2; i > 0; i--) {
			// 如果当前子数组小于零,则最大子数组必定不包含当前子数组
			if (temp < 0) {
				temp = 0;
				end2 = i;
			}
			temp += array[i];

			if (temp > max) {
				max = temp;
				start = i;
				end = end2;
			}
		}
		System.out.println("start at " + start + " end with " + end + ". Max sum is " + max);
		return max;
	}
}



虽然思路有点对了,但这个程序还是有明显的问题,试一下这个序列: {8, -2, 4, -11, 9}

并且为什么不用升序,倒序看起来怪异。So you're really like descending order.

try my work : http://play.golang.org/p/EaTrXpWHqN


0 请登录后投票
论坛首页 Java企业应用版

跳转论坛:
Global site tag (gtag.js) - Google Analytics