C語言求最大子數組的算法淺談

摘要：隨著計算機的發展，算法在計算機方面已有廣泛的發展及應用。算法（Algorithm）是指解題方案的準確而完整的描述，是一系列解決問題的清晰指令，算法代表著用系統的方法描述解決問題的策略機制。也就是說，能夠對一定規范的輸入，在有限時間內獲得所要求的輸出。如果一個算法有缺陷，或不適合于某個問題，執行這個算法將不會解決這個問題。不同的算法可能用不同的時間、空間或效率來完成同樣的任務。一個算法的優劣可以用空間復雜度與時間復雜度來衡量。通過計算機語言進行編程，善于運用算法，可以減少代碼，提高效率，達到事倍功半的效果本文以C語言編程語言為編程工具，對于數組中求最大子數組的題目，通過窮舉法（暴力法）、分治法、分析法以及動態規劃法等算法進行了對比說明。

關鍵詞：算法? 最大子數組 暴力法 分治法 分析法? 動態規劃法

中圖分類號：? TP301.6? ? ? ? 文獻標志碼：A

1 C語言簡介

C語言（The C Programming Language）是一門面向過程、抽象化的通用程序設計語言，廣泛應用于底層開發。C語言僅僅產生少量的機器語言，而且不需要任何運行環境支持，就能夠運行的高效率程序設計語言。C語言具有跨平臺的特性，以一個標準規格寫出的C語言程序可在包括一些類似嵌入式處理器以及超級計算機等作業平臺的許多計算機平臺上進行編譯。

1972年，美國貝爾實驗室的 丹尼斯·里奇（D.M.Ritchie 設計出了C語言。美國電話電報公司（AT&T）貝爾實驗室于1978年正式發表了C語言。布萊恩·柯林漢（Brian Kernighan） 和 丹尼斯·里奇（Dennis Ritchie）出版了《The C Programming Language》一書。C語言編譯器普遍存在于各種不同的操作系統中，例如Microsoft Windows， Mac OS X， Linux， Unix等。C++、Objective-C、Java、C#等編程語言都深受C語言的設計影響。經過多年的改進和完善，C語言的標準先后有ANSI X3.159-1989 "Programming Language C（C89標準（ANSI C））、ISO/IEC 9899：1990 - Programming languages – C（C90標準）、ISO/IEC 9899：1990/Cor 1：1994（C94）標準、ISO/IEC 9899：1990/Amd 1：1995 - C Integrity（C95標準）、ISO/IEC 9899：1999 - Programming languages -- C （C99標準），目前最高標準為ISO/IEC 9899：2011 - Information technology -- Programming languages -- C ， （C11標準））。目前，長期占據著程序使用榜的前三名為C，C++，java同一系的語言。

1.1 C語言的優點

C語言自發布以來，深受廣大程序員的青睞，而經久不衰，是與其許多優點有關。C語言具有以下優點：語言簡潔緊湊、靈活方便;運算符以及數據類型豐富;編程表達方式靈活實用;可以允許直接訪問物理地址，能夠對硬件進行操作;不僅生成目標代碼質量高，程序執行效率高，而且可移植性好、表達力強等優點。

1.2 C語言的缺點

正如人無完人，金無赤金一樣，在長期的應用實踐中，大家也發現C語言也有一些缺點和不足。C語言在數據的安全性上有很大缺陷，主要表現在數據的封裝性上。此外C語言對變量的類型約束和語法限制不嚴格，對數組下標越界不作檢查等，影響了程序的安全性。從應用的角度，C語言比其他高級語言較難掌握。

2 算法簡述

2.1 算法的基本概念

算法（Algorithm）與程序設計以及數據結構（Data Structures）緊密相關，是解決一個問題的完整的步驟描敘，是解決問題的策略，規則，方法，算法的描敘形式多種多樣，常用的有自然語言、結構化流程圖、偽代碼和PAD圖等，其中最普遍的是流程圖。

瑞士計算機科學家Pascal之父Nicklaus Wirth（沃斯）提出的著名公式：“算法+數據結構=程序”（Algorithm+Data Structures=Programs）。數據結構值得是數據與數據之間的邏輯關系，算法則指的是解決特定問題的步驟和方法。算法可大致分為基本算法、數據結構的算法、數論與代數算法、計算幾何的算法、圖論的算法、動態規劃以及數值分析、加密算法、排序算法、檢索算法、隨機化算法、并行算法，厄米變形模型，隨機森林算法。

2.2 算法的特征

一個算法應該具有以下五個重要的特征：算法的基本特征歸納如下：

2.2.1 有窮性（Finiteness）是指算法必須能在執行有限個步驟之后終止;

2.2.2 確切性（Definiteness） 即算法的每一步驟必須有確切的定義;

2.2.3 輸入項（Input） 一個算法有0個或多個輸入，以描述運算對象的初始情況，所謂0個輸入是指算法本身給定出了初始條件;

2.2.4 輸出項（Output） 相對于輸入項，一個算法有一個或多個輸出，以反映對輸入數據加工后的結果。值得一提的是，沒有輸出的算法是毫無意義的;

2.2.5可行性（Effectiveness） 算法中執行的任何步驟都是可以被分解為基本的可執行的操作步驟，也就是說每個計算步驟都可以在有限時間內完成，因此同樣稱之為有效性。

3 求最大子數組的四種算法示例

數組是定義用來存儲個組同一種數據的構造，特定是只能存放一種類型的數據，數組里的數據稱為元素。數組可以是一維數組、二維數組以及多維數組。

最大連續子數組：假設給定一個數組Array[0，...，n-1]，該數組有n個元素，求Array的連續子數組，使得該子數組的和最大。

下面給出運用四種不同算法求最大連續子數組的解法。

3.1 窮舉法（暴力法）

或稱為暴力破解法，其基本思路是：對于要解決的問題，列舉出它的所有可能的情況，逐個判斷有哪些是符合問題所要求的條件，從而得到問題的解。

算法分析：直接求解Array[i，...j]的值;其中0<=i<n;i<=j<n，i，i+1，...，j-1，j的最大長度為n;即對數組內每一個數A[i]進行遍歷，然后遍歷以它們為起點的子數組，比較各個子數組的大小，找到最大連續子數組。代碼如下：

#include "stdafx.h"

//暴力法求最大子數組和問題

int _tmain（int argc， _TCHAR* argv[]）

{

int A[8] = { -6， 10， -5， -3， -7， -1， -1 };

int array_length = sizeof（A） / sizeof（A[0]）;//數組大小

int sum = 0;//記錄子數組的和

int low;//記錄子數組的底

int height;//記錄子數組的高

for （int i = 0; i < array_length; i++）

{

for （int j = i ; j < array_length; j++）

{

int subarraysum=0;//所遍歷出來的子數組的和

//計算遍歷的子數組之和

for （int k = i; k <= j; k++）

{

subarraysum += A[k];

}

//找出最大的子數組

if （subarraysum>sum）

{

sum = subarraysum;

low = i;

height = j;

}

}

}

printf（"%d? %d? %d"， low， height，sum）;//將結果打印出來

getchar（）;

return 0;

}

可以看到這段程序里面一共嵌套著三層循環，除了最外面的循環會循環n次外，內部的循環都比n次小，此程序的時間復雜度為O（n3）

3.2 分治法

分治法是把一個復雜的問題分成兩個或更多的相同或相似的子問題，再把子問題分成更小的子問題……直到最后子問題可以簡單的直接求解，原問題的解即子問題的解的合并。

算法分析：將數組從中間分開，這樣最大子數組要么完全在左半邊數組，要么完全在右半邊數組，要么跨立在分界點上。如果完全在左半邊數組或者右半邊數組的話，可以采用遞歸解決。如果跨立在分界點上，實際上是左半邊數組的最大后綴和右半邊數組的和。因此，從分界點向前掃，向后掃就可以了。代碼如下：

double? MaxaddSub（double *a， int from， int to）

{

if（to == from）

return a[from];

int middle = （from + to）/2;

double m1 = MaxaddSub（a，from，middle）;

double m2 = MaxaddSub（a，middle+1，to）;

int i， left = a[middle]， now=a[middle];

for（i = middle-1; i>=from; --i）

{

now += a[i];

left = max（now，left）;

}

int right = a[middle_1];

now = a[middle+1];

for（i = middle+2;i<= to; +=i）

{

now ==a[i];

right = max（now， right）;

}

double m3 = left + right;

return max（m1，m2，m3）;

}

分治法算法復雜度分析：首先已經知道算法的遞歸關系為：T（n）=2*T（n/2）+cn，c為常數。若n=2k，則有：

T（n）=2*T（n/2）+cn

=2*（2*T（n/4）+c*（n/2））+c*n=4*T（n/4）+2c*n

=4*（2*T（n/8）+c*（n/4））+2c*n）=8*T（n/8）+3c*n

=8*（2*T（n/16）+c*（n/8））+3c*n）=16*T（n/16）+4c*n

=……

=2k T（1）+kc*n

=cn+cnlog_2?n

若2k<n<2k+1，則T（2k）<T（n）<T（2k+1），所以可以得出算法的時間復雜度T（n）=O（nlogn）。由于本程序是在數組的原地址上面進行的，所以總體的控件復雜度為遞歸的時間復雜度+數組所占的空間為S（n）+S（logn）=S（n）。

3.3 分析法（邏輯推理的算法應用）

算法分析：定義數組A的前綴和p[i] = a[0] + a[1]+...+a[i]， 從i到j的子數組和s[i，j] = p[j]-p[i-1]（這里定義p[-1]=0）。算法過程如下：首先求一個數組A的i前綴的和p[i]，遍歷i，這里0<=i<=n-1，那么p[i]=p[i-1]+A[i]然后計算p[i]-p[j]，遍歷i，同樣0<=i<=n-1，求一個最小值m，m的含義到當前i為止，從0到i-1這段最小的值，值的初始值設定為0（p[-1]=0），然后遍歷p[0，...，i-1]，更新m。則p[i]-m即為以a[i]結尾的數組中最大的子數組。關鍵代碼如下：

int m=0;

for（int i=0;i<n;==i）

{

if（a[i] - m > MaxV）

MaxV = a[i] - m;

if（m < a[i]）

m = a[i];

}

由于以上兩步都是線性的，因此，時間復雜度為O（n）。

3.4 動態規劃法

動態規劃是一種在數學和計算機科學中使用的，用于求解包含重疊子問題的最優化問題的方法。其基本思想是，將原問題分解為相似的子問題，在求解的過程中通過子問題的解求出原問題的解。動態規劃的思想是多種算法的基礎，被廣泛應用于計算機科學和工程領域。

算法分析：假定S[i]為以A[i]結尾的數組中和最大的子數組，那么，S[i+1]=max（S[i]+A[i+1]，A[i+1]）），S[0]=A[0]，i（0<=i<n-1）。代碼如下：

#include <stdlib.h>

#include? <stdio.h>

int main（）

{

int count;

int a[100];

int b[100];

int i;

int max;

scanf（"%d"，&count）;

for（i=0; i<count; i++）

{

scanf（"%d"，&a[i]）;

}

b[0]=a[0];

max=b[0];

for（i=1; i<count; i++）

{

if（b[i-1]>0）

b[i]=b[i-1]+a[i];

else

b[i]=a[i];

if（b[i]>max）

max=b[i];

}

printf（"%d＼n"，max）;

return 0;}

該算法的時間復雜度O（n）。

4 結束語

算法可以說包羅萬象，諸如推理、邏輯、演繹、歸納、類別等方法。常用的算法有遞推法、遞歸法、窮舉法、貪心算法、分治法、動態規劃法、迭代法、分支界限法、回溯法等諸多方法。一個算法的好壞直接決定了這個程序的好壞，合理地運用算法，能夠獲得更高的效率。掌握和熟悉這些算法技巧，對于計算機編程設計是大有裨益的。

參考文獻：

[1] 譚浩強.C程序設計：第4版[M].北京：清華大學出版社，2010.

[2] 蘇小紅，孫志崗，陳惠鵬.C語言大學實用教程[M].北京：電子工業出版社，2012.

[3] 毛廣敏.常用C語言排序算法解析[J].軟件導刊，2012 ， 11（11）：51-54.

[4] Michael Wong，IBM XL 編譯器中國開發團隊.深入理解C++11： C++11新特性解析與應用[M].北京：機械工業出版社，2013.

[5] 徐鳳生，黃超，謝玉華.C語言程序設計[M].北京：中國鐵道出版社，2015.

[6] Wirth Niklaus.算法+數據結構=程序[M].曹德和，劉椿年，譯.北京：科學出版社，1984.

[7] Cormen Thomas H. ，Leiserson Charles E. ，Rivest Ronald L. ，et al.算法導論：第3版[M].殷建平，徐云，王剛，譯 .北京：機械工業出版社，2015.

[8] 鐘志水，姚珺.大學計算機應用基礎[M].重慶：重慶大學出版社，2012：213-214.

劉柱（1971—），男，漢族，甘肅蘭州人，大學本科，工程師，主要從事網絡工程軟件開發工作。