求一个数组中最大的相邻元素之和

本文来自博客：http://blog.csdn.net/gaoyusi4964238/archive/2010/05/18/5605123.aspx

 

问题描述：

给定一个数据，求数据中相邻元素的最大和。例如：对于数组[5,-6,5,3,6,-8]，其相邻元素最大和为14（5+3+6）。

算法实现如下：

view plaincopy to clipboardprint?package test;     import java.util.Random;     import org.junit.Test;     public class TestAlgorithm {         /**       * 对于数组分为两个大小基本相等的部分，那么最大和集必然出现在以下三种情况下：       * <p>1.最大和集出现在前半部分内，或者是整个前半部分;       * <p>2.最大和集出现在后半部分内，或者是整个后半部分;       * <p>3.如果过既不出现在前半部分，也不出现在后半部分，那么最大和必然横跨前半部分和后半部分，       * 所以前半部分(假设a)和后半部分(假设b)的分割点(假设i)必然包含在最大和集中，那么这时候只需要以i       * 为起点向前求其最大和集(c1)，向后求其最大和集(c2),那么这种情况下最大和集为c1+c2;       * <p>所以最大和集的求法即可采用分治算法，递归求出数组前半部分，后半部分，和整个部分的最大值即可。       */      public int divideAndConquerSum(int[] a,int low,int high){           if(low>high)               return 0;                      if(low==high)               return max(0,a[low]);                      //求出在[low,high]内包含a[mid]的最大sum           int mid=(low+high)/2;           int isum=0;           int lsum=0;           int rsum=0;           for(int i=mid;i>=low;i--){               isum+=a[i];               lsum=max(isum,lsum);           }           isum=0;           for(int i=mid+1;i<=high;i++){               isum+=a[i];               rsum=max(isum,rsum);           }                      return  max(lsum+rsum,divideAndConquerSum(a,low,mid),divideAndConquerSum(a,mid+1,high));       }              /**       * 扫描算法       */      public int scanningSum(int[] a){           int sum=0;           int tmpSum=0;           for(int i=0;i<a.length;i++){               //如果前i位之和为负数，那么说明前i位不可能包含在最大和集中，重置tmpSum               tmpSum=max(tmpSum+a[i],0);               sum=max(tmpSum,sum);           }           return sum;       }              public int max(int a,int b){           return a>b?a:b;       }              public int max(int a,int b,int c){           //System.out.println("a:"+a+";b:"+b+";c:"+c);           return max(a,max(b,c));       }              @Test      public void test(){           Random random=new Random();           int [] a=new int[random.nextInt(10)];           for(int i=0;i<a.length;i++){               a[i]=random.nextInt(100)-random.nextInt(100);               System.out.print(a[i]+",");           }           System.out.println("数组长度:"+a.length);                      int dMax=divideAndConquerSum(a,0,a.length-1);           System.out.println("分治算法："+dMax);           int sMax=scanningSum(a);           System.out.println("扫描算法："+dMax);       }   }