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 求最大子数组的四种算法示例

　　数组是定义用来存储个组同一种数据的构造，特定是只能存放一种类型的数据，数组里的数据称为元素。数组可以是一维数组、二维数组以及多维数组。