問題描述：一個有n個元素的數(shù)組，這n個元素可以是正數(shù)也可以是負數(shù)，求最大子數(shù)組的和。
方法1：蠻力法
思路：最簡單也是最容易想到的方法就是找出所有子數(shù)組，然后求所有子數(shù)組的和，在所有子數(shù)組的和中取最大值。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
/** * 方法1（蠻力法）：兩次循環(huán)求最大子數(shù)組之和 */ public static int maxSubArray1(int[] a){ int i,j; int ThisSum=0; int MaxSum=0; for (i = 0; i < a.length; i++) { ThisSum=a[i]; for(j=i+1;j<a.length;j++){ ThisSum+=a[j]; if(ThisSum>MaxSum){ MaxSum=ThisSum; } } } return MaxSum; } |
方法2：優(yōu)化的動態(tài)規(guī)劃
思路：首先可以根據(jù)數(shù)組的最后一個元素a[n-1]與最大子數(shù)組的關(guān)系分為以下三種情況：
1) 最大子數(shù)組包含a[n-1]，即以a[n-1]結(jié)尾。
2) a[n-1]單獨構(gòu)成最大子數(shù)組。
3) 最大子數(shù)組不包含a[n-1]，那么求a[1,...,n-1]的最大子數(shù)組可以轉(zhuǎn)換為求a[1,...,n-2]的最大子數(shù)組。
通過上述分析可以得出如下結(jié)論：假設(shè)已經(jīng)計算出(a[0],...a[i-1])最大的一段數(shù)組和為All[i-1]，同時也計算出(a[0],...a[i-1])中包含a[i-1]的最大的一段數(shù)組和為End[i-1]，
則可以得出如下關(guān)系：All[i-1]=max{a[i-1],End[i-1],All[i-1]}。利用這個公式和動態(tài)規(guī)劃的思想解決問題。(代碼中還解決了起始位置，終止位置的問題)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
|
/** * 方法2：優(yōu)化的動態(tài)規(guī)劃方法 * nEnd就是通過“數(shù)組依次相加加到a[i]，然后與a[i]做比較”得來的，保存較大的。因為如果前面的數(shù)加到a[i] * 還沒有a[i]本身大，那么前面的數(shù)也就對最大子數(shù)組和沒有貢獻。厲害 * nAll就是記錄一下之前的新得到的nEnd和自身之前誰更大 */ public static int max(int m,int n){ return m>n?m:n; } public static int maxSubArray2(int[] a){ int nAll=a[0];//有n個數(shù)字數(shù)組的最大子數(shù)組之和 int nEnd=a[0];//有n個數(shù)字數(shù)組包含最后一個元素的子數(shù)組的最大和 for (int i = 1; i < a.length; i++) { nEnd=max(nEnd+a[i],a[i]); nAll=max(nEnd, nAll); } return nAll; } private static int begin=0; private static int end=0; /** * 求出最大子數(shù)組的開始begin，結(jié)尾end，以及整個子數(shù)組 */ public static int maxSubArray3(int[] a){ int maxSum=Integer.MIN_VALUE; int nSum=0; int nStart=0; for (int i = 0; i < a.length; i++) { if(nSum<0){ nSum=a[i]; nStart=i; } else{ nSum+=a[i]; } if(nSum>maxSum){ maxSum=nSum; begin=nStart; end=i; } } return maxSum; } |
以上就是本文的全部內(nèi)容，希望本文的內(nèi)容對大家的學(xué)習(xí)或者工作能帶來一定的幫助，同時也希望多多支持服務(wù)器之家！
原文鏈接：http://www.cnblogs.com/winorgohome/p/6038320.html
