程序员编程艺术：第七章、求连续子数组的最大和
by v_JULY_v
at 2011-05-25 09:30:00
original http://blog.csdn.net/v_JULY_v/archive/2011/05/25/6444021.aspx
程序员面试题狂想曲：第七章、求子数组的最大和作者：July出处：前奏 我更愿意更多的人和我一样，把本狂想曲系列中的任何一道面试题当做一道简单的编程题或一个实质性的问题来看待，在阅读本狂想曲系列的过程中，希望你能尽量暂时放下所有有关面试的一切包袱，潜心攻克每一道“编程题”，在解决编程题的过程中，好好享受编程带来的无限乐趣，与思考带来的无限激情。第一节、求子数组的最大和3.求子数组的最大和题目描述：输入一个整形数组，数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。求所有子数组的和的最大值。要求时间复杂度为O(n)。例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5，和最大的子数组为3, 10, -4, 7, 2，因此输出为该子数组的和18。分析：这个问题在各大公司面试中出现频率之频繁，被人引用次数之多，单凭这点，就没有理由不