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

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

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

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

　　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 求最大子數組的四種算法示例

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