精华帖 (1) :: 良好帖 (0) :: 新手帖 (2) :: 隐藏帖 (0)
|
|
---|---|
作者 | 正文 |
发表时间:2012-05-04
如果是最大的子数组和的话,应该就是所有正数的的那个子数组吧
|
|
返回顶楼 | |
发表时间:2012-05-04
hiloo 写道 这种贴也可以上首页?javaEye现在是疯了
看起来简单,但是你看吧,这么多回帖的,还有帖代码的,有几个时间复杂度控制在O(n)了? 所以这个题对广大苦力的教育意义还是比较深远的。 |
|
返回顶楼 | |
发表时间: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; } } |
|
返回顶楼 | |
发表时间: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; } } |
|
返回顶楼 | |
发表时间: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 |
|
返回顶楼 | |
发表时间:2012-05-05
楼主,你这个是要找最大子序列吧?
|
|
返回顶楼 | |
发表时间: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; } |
|
返回顶楼 | |
发表时间: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; } } |
|
返回顶楼 | |
发表时间: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); } } |
|
返回顶楼 | |
发表时间: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 |
|
返回顶楼 | |