目錄
一、題目
二、算法求解
1、蠻力算法
偽代碼
?算法分析
程序
2、分治策略
偽代碼
算法分析
程序
3、動(dòng)態(tài)規(guī)劃算法
偽代碼
算法分析
程序
一、題目
設(shè)A=<a1,a2,...,an>是n個(gè)整數(shù)的序列，稱<ai,....,aj>為該序列的連續(xù)子序列，其中1<=i<=j<=n，子序列的元素之和稱為A的子段和：
例如，A=<-2,11,-4,13,-5,-2>，那么它的子段和如下：
長(zhǎng)度為1的子段和有：-2,11,-4,13,-5,-2
長(zhǎng)度為2的子段和有：9,7,9,8,-7
長(zhǎng)度為3的子段和有：5,20,4,6
長(zhǎng)度為4的子段和有：18,15,2
長(zhǎng)度為5的子段和有：13,13
長(zhǎng)度為6的子段和有：11
其中的最大子段和為：11-4+13=20
則最大子段和問(wèn)題為：
給定n個(gè)整數(shù)的序列A=<a1,a2,...,an>，求
二、算法求解
1、蠻力算法
通過(guò)枚舉A的所有連續(xù)子序列并且求和，通過(guò)比較找出具有最大和的子序列。
偽代碼
//算法 Enumerate
//輸入：數(shù)組A[1..n]
//輸出：sum,first,last?? //sum為最大子段和，first與last分別是和的首末位置
- ?????
- ???????????????
- ??????????????
- ?????
- ?????
- ???????????????
- ???????????????
?算法分析
3個(gè)for循環(huán)，每次執(zhí)行O(n)次，循環(huán)內(nèi)部是常數(shù)操作，所以該算法的時(shí)間復(fù)雜度為
程序
//算法3.8 Enumerate
//輸入：數(shù)組A[1..n]
//輸出：sum,first,last
#include<stdio.h>
#include<stdlib.h>
void Enumerate (int a[],int n)
{
int sum = 0;
int i,j,k;
int first,last;
for(i = 0;i < n; i++){
for(j = i;j < n;j++){
int thissum = 0;
for(k = i;k <= j; k++){
thissum = thissum + a[k];
}
if(thissum > sum){
sum = thissum;
first = i;
last = j;
}
}
}
printf("數(shù)組A的最大連續(xù)子段和為A[%d..%d]=%d",first+1,last+1,sum);
}
int main()
{
int A[6]={-2,11,-4,13,-5,-2};
int i;
for(i = 0;i < 6;i++)
{
printf("%d ",A[i]);
}
printf("\n");
Enumerate(A,6);
return 0;
}2、分治策略
與最鄰近點(diǎn)對(duì)的算法（參考之前的文章）類似，我們可以在 n/2的位置將 A 劃分成A1和 A2前后兩半，于是 A 的最大子段和可能是三種情況：
- 出現(xiàn)在 A1部分
- 出現(xiàn)在 A 部分，
- 出現(xiàn)在橫跨兩邊的中間部分
前兩種情況恰好對(duì)應(yīng)于兩個(gè)規(guī)模減半的子問(wèn)題，第三種情況需要特殊處理一下，設(shè)原問(wèn)題的輸人是 A [1...n]，中間分點(diǎn) k = n /2，那么前半部分子問(wèn)題的輸人是 A [1...k]，后半部分子問(wèn)題的輸人是 A [ k +1，n]。在第三種情況下，設(shè)這個(gè)最大和是 A [ p .. q ]，那么, ，從 A [ p ］到 A [ k ］的元素都在 A1 中，從 A [ k 十1］到 A [ q ］的元素都在 A2 中，我們只需要從 A [ k ］和 A [ k +1］分別向前和向后求和即可，比如以 A [ p ...k ］的計(jì)算為例，依次計(jì)算 A [ k .. k ], A [ k-1, k ],.., A [1...k]，記下其中最大的和 S1 ，即 A [ p ... k ]，對(duì)右半部可以同樣處理，只不過(guò)掃描方向相反，得到的 S2 就是 A [ k+1... q ］的元素之和，當(dāng)兩個(gè)方向的掃描都完成之后,S1+S2 就是橫跨中心的最大和，其邊界從p到q。這三種情況都計(jì)算完成以后，通過(guò)比較就可以確定 A 的最大子段和
偽代碼
//MaxSubSum(A,left,right) 【分治算法】
//輸入：數(shù)組A,left,right分別是A的左右邊界，1<=left<=right
//輸出：A的最大子段和sum及其子段的前后邊界
算法分析
設(shè)算法對(duì)規(guī)模為的輸人運(yùn)行時(shí)間是 T ( n )，行3和行4是遞歸調(diào)用，每個(gè)子問(wèn)題是原來(lái)問(wèn)題規(guī)模的一半，因此需要2T( n /2）時(shí)間，行5和行6的處理需要掃描A的每個(gè)元素，總計(jì)需要O(n)時(shí)間，于是遞歸方程為：
該方程的解為：
程序
//算法3.9 MaxSubSum(A,left,right) 【分治算法】
//輸入：數(shù)組A,left,right分別是A的左右邊界，1<=left<=right
//輸出：A的最大子段和sum及其子段的前后邊界
#include<stdio.h>
#include<stdlib.h>
typedef struct max_info{
int low;
int high;
int sum;
};
struct max_info MaxSubSum(int a[],int left,int right)
{
struct max_info maxinfo;
maxinfo.sum = 0;
int i;
if(left == right){
maxinfo.sum = a[left]>0 ? a[left] : 0;
maxinfo.high = right;
maxinfo.low = right;
return maxinfo;
}
else{
struct max_info leftinfo;//左側(cè)
struct max_info rightinfo;//右側(cè)
struct max_info croseinfo;//跨越
int center = (left + right) / 2;
leftinfo = MaxSubSum(a, left, center);
rightinfo = MaxSubSum(a, center + 1, right);
int s1 = 0;
int suml = 0;
for(i = center; i >= left; i--)
{
suml += a[i];
if(suml > s1)
{
s1 = suml;
croseinfo.low = i;
}
}
int s2 = 0;
int sumr = 0;
for(i = center + 1; i < right; i++)
{
sumr += a[i];
if(sumr > s2)
{
s2 = sumr;
croseinfo.high = i;
}
}
croseinfo.sum = s1 + s2;
if(croseinfo.sum < leftinfo.sum){
maxinfo.sum = leftinfo.sum;
maxinfo.high = leftinfo.high;
maxinfo.low = leftinfo.low;
}
if(croseinfo.sum < rightinfo.sum){
maxinfo.sum = rightinfo.sum;
maxinfo.high = rightinfo.high;
maxinfo.low = rightinfo.low;
} else{
maxinfo.sum = croseinfo.sum;
maxinfo.high = croseinfo.high;
maxinfo.low = croseinfo.low;
}
}
return maxinfo;
}
int main()
{
struct max_info maxinfo;
int A[6]={-2,11,-4,13,-5,-2};
int i;
for(i = 0;i < 6;i++)
{
printf("%d ",A[i]);
}
printf("\n");
maxinfo = MaxSubSum(A,0,5);
printf("數(shù)組A的最大連續(xù)子段和為：A[%d..%d]=%d\n",maxinfo.low+1,maxinfo.high+1,maxinfo.sum);
return 0;
}
3、動(dòng)態(tài)規(guī)劃算法
為了得到更高效的算法，我們需要在子問(wèn)題之間建立一個(gè)簡(jiǎn)單的遞推關(guān)系，因此定義一個(gè)優(yōu)化函數(shù)
?對(duì)于數(shù)組A=<2,-5,8,11,-3,4,6>，其優(yōu)化函數(shù)為：C[1]=2、C[2]=-3、C[3]=8、C[4]=19、C[5]=16、C[6]=20、C[7]=26
在這種優(yōu)化函數(shù)中，C [ i +1］可以通過(guò) C[ i ] 直接得到，因?yàn)槿绻?A [1...? i +1 ］的子段 A [ k .. i +1］是使得 C [ i ＋1 ]達(dá)到最大和的子段，那么 A [ k ... i ］一定是使得 C [ i ]達(dá)到最大和的子段．如若不然，存在一個(gè)使得 C[ i ]達(dá)到更大和的子段 A [ t ... i ]，那么在 A [ t ... i ］后面加上 A[ i+1 ]所得到的子段 A [ t ... i +1］之和將大于 C [ i +1].這與 C [ i 十1］是 A [1.. i +1］以元素 A [ i +1］作為最后元素的最大子段和矛盾．這恰好驗(yàn)證了這樣定義的優(yōu)化函數(shù)滿足優(yōu)化原則于是，我們?cè)诳紤]怎樣選擇才能使得 C [ i +1］達(dá)到最大值時(shí)，只要考慮一個(gè)問(wèn)題：是否需要把 C [ i ]加到 A [ i +1上？而這取決于 C [ i ]是否大于0．
那么遞推關(guān)系為：
???? 若A[1]>0,否則C[1]=0
根據(jù)上面的遞推公式，得到C[1]，C[2]，C[3].....C[n，]恰好枚舉了以任何元素為最后元素的所有子段的最大和，我們要找到所求問(wèn)題的最大子段和，就要對(duì)上面n個(gè)子段和進(jìn)行比較，找到其中最大和。
偽代碼
//MaxSum(A,n) 【動(dòng)態(tài)規(guī)劃】
//輸入：數(shù)組A
//輸出：最大子段sum，子段的最后位置c文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-820951.html
- ??????
- ??????
- ??????
- ??????
- ??????
- ???????????????????
算法分析
MaxSum(A,n) 算法只有一個(gè)for循環(huán)，執(zhí)行次數(shù)為O(n)，循環(huán)體內(nèi)都是常數(shù)次運(yùn)算，因此算法復(fù)雜度為O(n)文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-820951.html
程序
//算法3.10 MaxSum(A,n) 【動(dòng)態(tài)規(guī)劃】
//輸入：數(shù)組A
//輸出：最大子段sum，子段的最后位置c
#include<stdio.h>
#include<stdlib.h>
void MaxSum(int A[], int n)
{
int sum = 0;
int b = 0;
int i,c;
for(i = 0;i < n;i++)
{
if(b > 0)
b= b+A[i];
else
b = A[i];
if(b > sum)
{
sum = b;
c = i;
}
}
printf("數(shù)組A的最大連續(xù)子段和為：%d,且子段最后位置為：%d",sum,c+1);
}
int main()
{
int A[7]={2,-5,8,11,-3,4,6};
int i;
for(i = 0;i < 7;i++)
{
printf("%d ",A[i]);
}
printf("\n");
MaxSum(A,7);
return 0;
}到了這里，關(guān)于最大子段和——用蠻力算法，分治策略，動(dòng)態(tài)規(guī)劃算法三種求法（C語(yǔ)言）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
