問題描述：一個有n個元素的數組，這n個元素可以是正數也可以是負數，求最大子數組的和。
方法1：蠻力法
思路：最簡單也是最容易想到的方法就是找出所有子數組，然后求所有子數組的和，在所有子數組的和中取最大值。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
/** * 方法1（蠻力法）：兩次循環求最大子數組之和 */ 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：優化的動態規劃
思路：首先可以根據數組的最后一個元素a[n-1]與最大子數組的關系分為以下三種情況：
1) 最大子數組包含a[n-1]，即以a[n-1]結尾。
2) a[n-1]單獨構成最大子數組。
3) 最大子數組不包含a[n-1]，那么求a[1,...,n-1]的最大子數組可以轉換為求a[1,...,n-2]的最大子數組。
通過上述分析可以得出如下結論：假設已經計算出(a[0],...a[i-1])最大的一段數組和為All[i-1]，同時也計算出(a[0],...a[i-1])中包含a[i-1]的最大的一段數組和為End[i-1]，
則可以得出如下關系：All[i-1]=max{a[i-1],End[i-1],All[i-1]}。利用這個公式和動態規劃的思想解決問題。(代碼中還解決了起始位置，終止位置的問題)
|
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：優化的動態規劃方法 * nEnd就是通過“數組依次相加加到a[i]，然后與a[i]做比較”得來的，保存較大的。因為如果前面的數加到a[i] * 還沒有a[i]本身大，那么前面的數也就對最大子數組和沒有貢獻。厲害 * 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個數字數組的最大子數組之和 int nEnd=a[0];//有n個數字數組包含最后一個元素的子數組的最大和 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; /** * 求出最大子數組的開始begin，結尾end，以及整個子數組 */ 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; } |
以上就是本文的全部內容，希望本文的內容對大家的學習或者工作能帶來一定的幫助，同時也希望多多支持服務器之家！
原文鏈接：http://www.cnblogs.com/winorgohome/p/6038320.html
