給定n個整數(shù)（可能為負(fù)數(shù)）組成的序列a[1],a[2],a[3],…,a[n],求該序列如a[i]+a[i+1]+…+a[j]的子段和的最大值。當(dāng)所給的整均為負(fù)數(shù)時定義子段和為0合是，依此定義了罪，所求的最優(yōu)值為： Max{0,a[i]+a[i+1]+…+a[j]},1<=i<=j<=n 例如，當(dāng)（a[1],a[2],a[3],a[4],a[5],a[6]）}=(-2,11,-4,13,-5,-2)時聪全，最大子段和為20泊藕。

最大子段和是動態(tài)規(guī)劃中的一種。

import java.util.Random;
import java.util.Scanner;

public class maxSum {
  public static void main(String[] args){

    Scanner scan = new Scanner(System.in);
    Random rd = new Random();

    System.out.println("請輸入數(shù)據(jù)規(guī)模n（10的倍數(shù)）：");
    int n = scan.nextInt();
    int[] a = new int[n];
    for(int i=0; i<n; i++){
    a[i] = rd.nextInt(20)-10;  
  }//初始化數(shù)組难礼，生成-10~10的隨機(jī)數(shù)
  
  /*
  * test暴力法
  */
  long startMili1 = System.currentTimeMillis();
  maxSum ms1 = new maxSum();
  System.out.println("最大子序列和：" + ms1.maxSum(a));
  long endMili1 = System.currentTimeMillis();
  System.out.println("暴力法總耗時："+ (endMili1 - startMili1));
  
  /*
  * test優(yōu)化后的暴力法
  */
  long startMili2 = System.currentTimeMillis();
  maxSum ms2 = new maxSum();
  System.out.println("最大子序列和：" + ms2.maxSumBF(a));
  long endMili2 = System.currentTimeMillis();
  System.out.println("總耗時："+ (endMili2 - startMili2));
   
  /*
  * test分治算法
  */
  long startMili3 = System.currentTimeMillis();
  maxSum ms3 = new maxSum();
  System.out.println("最大子序列和：" + ms3.maxSumFZ(a));
  long endMili3 = System.currentTimeMillis();
  System.out.println("總耗時："+ (endMili3 - startMili3));

  /*
  * test動態(tài)規(guī)劃算法
  */
  long startMili4 = System.currentTimeMillis();
  maxSum ms4 = new maxSum();
  System.out.println("最大子序列和：" + ms4.MaxSumDynamic(a));
  long endMili4 = System.currentTimeMillis();
  System.out.println("總耗時："+ (endMili3 - startMili3));

  }

  //暴力法(O(n^3))
  public static int maxSum(int a[]){
  int n = a.length - 1;
  int sum = 0;
  for(int i=1; i<=n; i++){
    for(int j=1; j<=n; j++){
      int thissum = 0;
      for(int k=i; k<=j; k++){
        thissum += a[k];
      }
      if(thissum>sum){
        sum = thissum;
      }
    }
  }
  return sum;
}

//優(yōu)化后的暴力法 (O(n^2))
public int maxSumBF(int a[]){
  int n = a.length - 1;
  int sum = 0;
  for(int i=1; i<=n; i++){
    int thissum = 0;
    for(int j=i; j<=n; j++){
      thissum += a[j];
      if(thissum>sum){
        sum = thissum;
      }
    }
  }
  return sum;
}

  //分治算法(n log(n))
  private static int maxSubSum(int a[], int left, int right){
  int sum = 0;
  if(left == right){
     sum = a[left]>0?a[left]:0;
  }else{
    int center = (left + right)/2;
    int leftsum = maxSubSum(a,left,center);
    int rightsum = maxSubSum(a,center+1,right);
    int s1 = 0;
    int lefts = 0;
    for(int i=center; i>=left; i--){
      lefts += a[i];
      if(lefts>s1){
      s1 = lefts;
    }
  }
  int s2 = 0;
  int rights = 0;
  for(int i=center+1; i<=right; i++){
    rights += a[i];
    if(rights>s2){
      s2 = rights;
    }
  }
    sum = s1 + s2;
    f(sum<leftsum){
      sum = leftsum;
    }
    if(sum<rightsum){
      sum = rightsum;
    }
  }
  return sum;
}

public static int maxSumFZ(int a[]){
  return maxSubSum(a,1,a.length-1);
}

//動態(tài)規(guī)劃算法(O(n))
public static int MaxSumDynamic(int a[]){
  int n = a.length-1;
  int sum = 0,b = 0;
  for(int i=1; i<=n; i++){
    if(b>0){
      b += a[i];
    }else{
    b = a[i];
  }
  if(b>sum){
    sum = b;
  }
 }
return sum;
}
}