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—），男，汉族，甘肃兰州人，大学本科，工程师，主要从事网络工程软件开发工作。