一.問題

例：求數(shù)列的最大子段和。 給定n個元素的整數(shù)列（可以能為負(fù)整數(shù)）,a1,a2,…,an。求數(shù)列的字段，使其和最大。

例如：當(dāng)(a1, a2, a3, a4, a5, a6)=(-2, 11, -4, 13, -5, -2)時，最大子段和為sum(11-4+13)=20。

二.解決方法

我這里采用兩種方法：①遍歷的方法? ②分治法

①遍歷法

原理分析：遍歷該數(shù)組，每遍歷一個i元素就判斷temp+a[i]是否大于a[i],如果大于就更新temp=temp+a[i],否則temp=a[i],最后temp跟當(dāng)前最大子序列和maxsum比較，如果大于，則maxsum=temp；否則不更新maxsum;最后遍歷完，直接返回maxsum.

遍歷法的c語言源碼：

#include<stdio.h> //類似于01背包問題 int start,end; int MaxSubsequenceSum( int A[], int n) {int tempsum = 0;int maxSum = 0;int tstart=0,tend=0;for (int j = 0;j < n;j++) //遍歷數(shù)組{ if((tempsum + A[j]) > A[j]){ //判斷臨時最大和+一個當(dāng)前元素是否大于當(dāng)前元素，如果大于，則把當(dāng)前元素加進(jìn)來，更新臨時最大和，否則臨時最大和更新為當(dāng)前元素tempsum=tempsum + A[j];tend=j; //更新末尾位置 }else{ //如果臨時最大和+一個當(dāng)前元素小于當(dāng)前元素，則更新臨時最大和tempsum=A[j];tstart=j; //更新起始位置}if (tempsum > maxSum){ // 通過當(dāng)前臨時最大和與上一個最大和作比較，如果大于則更新最大和maxSum = tempsum;start=tstart; //更新起始位置end=tend; //更新末尾位置}}return maxSum; } int main() {int maxSubSum,n,i;int a[101]; while(scanf("%d",&n)!=EOF){for(i=0;i<n;i++)scanf("%d",&a[i]);maxSubSum = MaxSubsequenceSum(a, n);printf("%d %d %d\n",maxSubSum,start,end);}return 0; }

②分治法

原理分析：此問題用二分法分解后的兩個子序列（子問題）并不獨立，因為有可能最長的連續(xù)不升數(shù)列正好存在于兩個子序列的連接位置。 ? ?

?如果將所給的序列a[1..n]分為長度相等的2段a[1--(n/2)]和a[(n/2)+1--n],則a[1--n]的最長連續(xù)不升數(shù)列有3種情況：

1) a[1..n]的最長連續(xù)不升數(shù)列與a[1..(n/2)]的最長連續(xù)不升數(shù)列相同;

2) a[1..n]的最長連續(xù)不升數(shù)列與a[(n/2)+1..n]的最長連續(xù)不升數(shù)列相同;

3) a[1..n]的最長連續(xù)不升數(shù)列為∑a[k],且1≤i≤(n/2),(n/2),(n/2)+1≤j≤n。

情況1和情況2可分別遞歸求得。 對于情況3,如果不在情況1和情況2中，則a[(n/2)]與a[(n/2)+1]一定在最優(yōu)子序列中。因此,我們可以計算出a[i..(n/2)]的最大值s1;并計算出a[(n/2)+1..j]中的最大值s2。則s1+s2即為出現(xiàn)情況3時的最優(yōu)值。

c語言源碼：

#include<stdio.h> #define max 100 int start=0; int end=0; int minsum(int a[], int left, int right) {int s,s0, s1, lf, rt;if (left == right)return a[left];else {int mid = (left + right)/2;int leftsum = minsum(a, left, mid); //左子序列最大和int rightsum = minsum(a, mid + 1, right); //右子序列最大和s0 = 0; //左邊臨時和lf = 0;for(int i = mid; i >= 0; i--) {lf += a[i];if (lf > s0) { //加上當(dāng)前的數(shù)如果大于左邊臨時和，則更新左邊臨時和s0 = lf;start = i; //起始點}}s1 = 0; //右邊臨時和rt = 0;for(i = mid + 1;i <= right; i++){rt += a[i];if (rt > s1) {s1 = rt;end = i; //末尾點}}s = s0 + s1;if (s< leftsum&&rightsum < leftsum)return leftsum;else if (s<rightsum&&rightsum>leftsum)return rightsum;else{return s;}} } int main() {int a[max],num,k=0,sum;while (scanf("%d", &num) != EOF) {k = 0;while (k<num){scanf("%d", &a[k]);k++;}sum = minsum(a, 0, num-1);printf("%d %d %d\n", sum,start,end);}return 0; }

?

總結(jié)

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

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