1、最大子段和：給定由n個整數(shù)組成的序列a1,a2,.an,求該序列子段和 的最大值！例如：(a1,a2,a3,a4,a5,a6)=(-2,11,-4,13,-5,-2),最大子段和為 11 + (-4) +13=20針對最大子段和求解，本此貢獻兩種算法，一個是分治算法，一個是動 態(tài)規(guī)劃。兩種算法的時間復(fù)雜度不一樣，分治算法是的時間復(fù)雜度為 T(n)=O(nlogn),動態(tài)規(guī)劃的時間復(fù)雜度為T(n)=O(n).本次博客不做具體 分析，只提供java代碼！ package com.liheng.algorithm;public class MaxSum (/* param args*功能：求最大子串

2、和*分別用分治法和動態(tài)規(guī)劃兩種方法，進行比較。更深入理解兩種算 法的相同點和不同點*/final static int maxLen =100;public static void main(String args) (/ TODO Auto-generated method stubMaxSum ms = new MaxSum();int a = (-2,11,-4,13,-5,-2);int n= a.length;System.out.println(分治算法：+ ms.maxSumBin(n-1, a);System.out.println(動態(tài)規(guī)劃算法：+ ms.MaxSumDin(

3、n-1, a);/*param nparam a分治算法求求最大字段和*/int maxSumBin(int n,int a) (return MaxSubSum(a, 0, n);int MaxSubSum(int a,int left,int right)(int sum=0;if(left=right) sum = aleft0?aleft:0;else(int center=(left+right)/2;分治遞歸，分別求左邊和右邊的最大值int leftSum二MaxSubSum(a, left, center);int rightSum = MaxSubSum(a, center+1, right);/*求兩邊的最大和，分別與兩邊的最大值進行比較*/int s1=0,lefts=0;for(int i=center;i=left;i-)(lefts+=ai;if(leftss1)s1=lefts;int s2=0,rights=0;for(int i=center+1;is2)s2=rights;sum=s1+s2;if(sumleftSum) sum=leftSum;if(sumrightSum) sum=rightSum;return sum;/*動態(tài)規(guī)劃求最大字段和*/int MaxSumDin(int n,int a)(int sum=0