C語言求最大子數(shù)組的算法淺談

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

　　關(guān)鍵詞：算法 最大子數(shù)組 暴力法 分治法 分析法 動態(tài)規(guī)劃法

　　《計算機(jī)應(yīng)用》創(chuàng)刊于1981年，是中國計算機(jī)學(xué)會會刊。以介紹計算機(jī)應(yīng)用技術(shù)為重點，以推動經(jīng)濟(jì)發(fā)展和科技進(jìn)步為宗旨，以促進(jìn)計算機(jī)開發(fā)應(yīng)用創(chuàng)新為目標(biāo)。

　　1 C語言簡介

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

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

　　1.1 C語言的優(yōu)點

　　C語言自發(fā)布以來，深受廣大程序員的青睞，而經(jīng)久不衰，是與其許多優(yōu)點有關(guān)。C語言具有以下優(yōu)點：語言簡潔緊湊、靈活方便;運(yùn)算符以及數(shù)據(jù)類型豐富;編程表達(dá)方式靈活實用;可以允許直接訪問物理地址，能夠?qū)τ布M(jìn)行操作;不僅生成目標(biāo)代碼質(zhì)量高，程序執(zhí)行效率高，而且可移植性好、表達(dá)力強(qiáng)等優(yōu)點。

　　1.2 C語言的缺點

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

　　2 算法簡述

　　2.1 算法的基本概念

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

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

　　2.2 算法的特征

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

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

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

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

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

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

　　3 求最大子數(shù)組的四種算法示例

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