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

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

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

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

　　1 C語言簡介

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

　　1972年，美國貝爾實驗室的 丹尼斯·里奇(D.M.Ritchie 設計出了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語言的設計影響。經過多年的改進和完善，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標準))。目前，長期占據(jù)著程序使用榜的前三名為C，C++，java同一系的語言。

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

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

　　1.2 C語言的缺點

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

　　2 算法簡述

　　2.1 算法的基本概念

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

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

　　2.2 算法的特征

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

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

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

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

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

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

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

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