一個(gè)有N個(gè)整數(shù)元素的一維數(shù)組( A[0], A[1], ... , A[n-2], A[n-1])，子數(shù)組之和的最大值是什么?(要求子數(shù)組的元素是連續(xù)的)

例子：有數(shù)組( -2, 5, 3, -6, 4, -8, 6)，則其子數(shù)組之和的最大值為8，其對(duì)應(yīng)的數(shù)組為(5,3)

解法一：采用直接法，記Sum[i...j]，為數(shù)組A中從第i到第j之間所有數(shù)之和，算出所有Sum，取其最大，代碼如下，時(shí)間復(fù)雜度O(N²)：

int maxSum1(int *A, int n) {int max = -1;int i, j, sum;for(i = 0; i < n; i++){sum = 0;for(j = i; j < n; j++){sum += A[j];if(sum > max )max = sum;}}return max; }

解法二：使用分治法，數(shù)組(A[0],A[1],...A(n-1)分為長度相等的兩段數(shù)組(A[0],...,A[n/2-1])以及(A[n/2],...,A[n-1])，分別求出這兩段數(shù)組各自的最大子段和，則原數(shù)組(A[0],A[1],...A(n-1)的最大子段和分為3種情況

1).(A[0],A[1],...A(n-1)的最大子段和與(A[0],...,A[n/2-1])的相同

2).(A[0],A[1],...A(n-1)的最大子段和與(A[n/2],...,A[n-1])的相同

3).(A[0],A[1],...A(n-1)的最大子段和跨過(A[0],...,A[n/2-1])與(A[n/2],...,A[n-1])-

1)和2)可以根據(jù)遞歸可得，3)只要計(jì)算出以A[n/2-1]為結(jié)尾的一段數(shù)組最大和s1=Sum1[i...n/2-1]和A[n/2]為開頭一段數(shù)組最大和s2=Sum2[n/2...j]，最后s=s1+s2.

這個(gè)算法滿足分值算法遞歸，總的時(shí)間復(fù)雜度O(N*log₂N)

解法三： 假設(shè)我們已經(jīng)知道(A[k].....A[n-1])最大的一段數(shù)組和為All[k]，并且已經(jīng)計(jì)算出在(A[k].....A[n-1])中包含A[k]的最大的一段數(shù)組和為Start[k]，那么可以推斷出All[k-1]=max{A[k-1]，A[k-1]+Start[k]，All[k]}，利用 動(dòng)態(tài)規(guī)劃思想 以及這樣的遞推公式，從后往前計(jì)算，代碼如下,時(shí)間復(fù)雜度O(N)：

int max(int x, int y) {return (x > y) ? x : y; }int maxSum2(int *A, int n) {int i;int All[n], Start[n];All[n-1] = A[n-1];Start[n-1] = A[n-1];for(i = n-2; i >= 0; i--){Start[i] = max(A[i], A[i]+Start[i+1]);All[i] = max(All[i+1], Start[i]);}return All[0]; } 對(duì)以上代碼進(jìn)行簡化，因?yàn)樽詈笏蟮降淖兞恐挥蠸tart[0]和All[0]，這樣可以反復(fù)用nStart和nAll，省略掉其他的變量，代碼如下

int max(int x, int y) {return (x > y) ? x : y; }int maxSum2_v(int *A, int n) {int i;int nAll, nStart;nAll = A[n-1];nStart = A[n-1];for(i = n-2; i >= 0; i--){nStart = max(A[i], A[i]+nStart);nAll = max(nAll, nStart);}return nAll; }

總結(jié)

以上是生活随笔為你收集整理的求数组的子数组之和的最大值的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。