- 浏览: 140900 次
- 性别:
- 来自: 上海
文章分类
最新评论
-
Jonathan樊:
请LZ不要简单的Copy过来,好吧?起码编辑一下啊~~该加的超 ...
直接拿来用!最火的Android开源项目 -
tao71535:
学习了、
不过为还是觉得看视频做例子、
比较好、、
Intent总结
题目:输入一个整形数组,数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和。求所有子数组的和的最大值。要求时间复杂度为O(n)。
例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5,和最大的子数组为3, 10, -4, 7, 2,因此输出为该子数组的和18。
分析:本题最初为2005年浙江大学计算机系的考研题的最后一道程序设计题,在2006年里包括google在内的很多知名公司都把本题当作面试题。由于本题在网络中广为流传,本题也顺利成为2006年程序员面试题中经典中的经典。
如果不考虑时间复杂度,我们可以枚举出所有子数组并求出他们的和。不过非常遗憾的是,由于长度为n的数组有O(n2)个子数组;而且求一个长度为n的数组的和的时间复杂度为O(n)。因此这种思路的时间是O(n3)。
很容易理解,当我们加上一个正数时,和会增加;当我们加上一个负数时,和会减少。如果当前得到的和是个负数,那么这个和在接下来的累加中应该抛弃并重新清零,不然的话这个负数将会减少接下来的和。基于这样的思路,我们可以写出如下代码。
参考代码:
讨论:上述代码中有两点值得和大家讨论一下:
· 函数的返回值不是子数组和的最大值,而是一个判断输入是否有效的标志。如果函数返回值的是子数组和的最大值,那么当输入一个空指针是应该返回什么呢?返回0?那这个函数的用户怎么区分输入无效和子数组和的最大值刚好是0这两中情况呢?基于这个考虑,本人认为把子数组和的最大值以引用的方式放到参数列表中,同时让函数返回一个函数是否正常执行的标志。
· 输入有一类特殊情况需要特殊处理。当输入数组中所有整数都是负数时,子数组和的最大值就是数组中的最大元素。
例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5,和最大的子数组为3, 10, -4, 7, 2,因此输出为该子数组的和18。
分析:本题最初为2005年浙江大学计算机系的考研题的最后一道程序设计题,在2006年里包括google在内的很多知名公司都把本题当作面试题。由于本题在网络中广为流传,本题也顺利成为2006年程序员面试题中经典中的经典。
如果不考虑时间复杂度,我们可以枚举出所有子数组并求出他们的和。不过非常遗憾的是,由于长度为n的数组有O(n2)个子数组;而且求一个长度为n的数组的和的时间复杂度为O(n)。因此这种思路的时间是O(n3)。
很容易理解,当我们加上一个正数时,和会增加;当我们加上一个负数时,和会减少。如果当前得到的和是个负数,那么这个和在接下来的累加中应该抛弃并重新清零,不然的话这个负数将会减少接下来的和。基于这样的思路,我们可以写出如下代码。
参考代码:
///////////////////////////////////////////////////////////////////////////// // Find the greatest sum of all sub-arrays // Return value: if the input is valid, return true, otherwise return false ///////////////////////////////////////////////////////////////////////////// bool FindGreatestSumOfSubArray ( int *pData, // an array unsigned int nLength, // the length of array int &nGreatestSum // the greatest sum of all sub-arrays ) { // if the input is invalid, return false if((pData == NULL) || (nLength == 0)) return false; int nCurSum = nGreatestSum = 0; for(unsigned int i = 0; i < nLength; ++i) { nCurSum += pData; // if the current sum is negative, discard it if(nCurSum < 0) nCurSum = 0; // if a greater sum is found, update the greatest sum if(nCurSum > nGreatestSum) nGreatestSum = nCurSum; } // if all data are negative, find the greatest element in the array if(nGreatestSum == 0) { nGreatestSum = pData[0]; for(unsigned int i = 1; i < nLength; ++i) { if(pData > nGreatestSum) nGreatestSum = pData; } } return true; }
讨论:上述代码中有两点值得和大家讨论一下:
· 函数的返回值不是子数组和的最大值,而是一个判断输入是否有效的标志。如果函数返回值的是子数组和的最大值,那么当输入一个空指针是应该返回什么呢?返回0?那这个函数的用户怎么区分输入无效和子数组和的最大值刚好是0这两中情况呢?基于这个考虑,本人认为把子数组和的最大值以引用的方式放到参数列表中,同时让函数返回一个函数是否正常执行的标志。
· 输入有一类特殊情况需要特殊处理。当输入数组中所有整数都是负数时,子数组和的最大值就是数组中的最大元素。
发表评论
-
微软等数据结构+算法面试100题
2011-02-23 17:48 1896微软等100题系列V0.1版终于结束了。 从2010年10月 ... -
百度11月4日网上笔试题及答案
2010-10-27 22:27 1190编程: 用C语言实现一个revert函数,它的功能是将输入的字 ... -
程序员面试题精选(18)-用两个栈实现队列
2009-08-15 12:01 1883题目:某队列的声明如 ... -
程序员面试题精选(17)-把字符串转换成整数
2009-08-15 12:00 2350题目:输入一个表示整数的字符串,把该字符串转换成整数并输出。例 ... -
程序员面试题精选(16)-O(logn)求Fibonacci数列
2009-08-15 11:59 2580题目:定义Fibonacci数列如下: / ... -
程序员面试题精选(15)-含有指针成员的类的拷贝
2009-08-15 11:57 1459题目:下面是一个数组 ... -
程序员面试题精选(14)-圆圈中最后剩下的数字
2009-08-15 11:55 2279题目:n个数字(0,1,…,n-1)形成一个圆圈,从数字0开始 ... -
程序员面试题精选(13)-第一个只出现一次的字符
2009-08-15 11:52 1695题目:在一个字符串中找到第一个只出现一次的字符。如输入abac ... -
程序员面试题精选(12)-从上往下遍历二元树
2009-08-15 11:49 1173题目:输入一颗二元树,从上往下按层打印树的每个结点,同一层中按 ... -
程序员面试题精选(11)-求二元查找树的镜像
2009-08-15 11:43 1185题目:输入一颗二元查 ... -
程序员面试题精选(10)-在排序数组中查找和为给定值的两个数字
2009-08-15 11:40 1880题目:输入一个已经按升序排序过的数组和一个数字,在数组中查找两 ... -
程序员面试题精选(09)-查找链表中倒数第k个结点
2009-08-15 11:30 1699题目:输入一个单向链表,输出该链表中倒数第k个结点。链表的倒数 ... -
程序员面试题精选(08)-求1+2+...+n
2009-08-08 21:18 2627题目:求1+2+…+n,要求 ... -
程序员面试题精选(07)-翻转句子中单词的顺序
2009-08-08 21:17 1869题目:输入一个英文句子,翻转句子中单词的顺序,但单词内字符的顺 ... -
程序员面试题精选(06)-判断整数序列是不是二元查找树的后序遍历结果
2009-08-08 21:15 1497题目:输入一个整数数组,判断该数组是不是某二元查找树的后序遍历 ... -
程序员面试题精选(05)-查找最小的k个元素
2009-08-08 21:14 1708题目:输入n个整数,输出其中最小的k个。 例如输入1,2,3, ... -
程序员面试题精选(04)-在二元树中找出和为某一值的所有路径
2009-08-08 21:12 1247题目:输入一个整数和一棵二元树。从树的根结点开始往下访问一直到 ... -
程序员面试题精选(02)-设计包含min函数的栈
2009-08-08 21:08 1768题目:定义栈的数据结构,要求添加一个min函数,能够得到栈的最 ... -
程序员面试题精选(01)-把二元查找树转变成排序的双向链表
2009-08-08 20:58 1900题目:输入一棵二元查 ...
相关推荐
程序员面试题精选程序员面试题精选程序员面试题程序员面试题精选精选
程序员面试题精选100题-何海涛 程序员 面试题 算法 数据结构
程序员考试试题---程序员考试教程 程序员考试试题---程序员考试教程
程序员面试题精选100题
简历模板-程序员-精选简历模板-程序员-精选简历模板-程序员-精选简历模板-程序员-精选简历模板-程序员-精选简历模板-程序员-精选简历模板-程序员-精选简历模板-程序员-精选简历模板-程序员-精选简历模板-程序员-精选...
程序员面试题精选100题
java程序员面试题150例 java常见面试题 java工程师面试题 java面试题大全 带搜索功能,能非常方便的查找到你想要了解的 java面试题目 推荐大家下载。
程序员面试题精选100题程序员面试题精选100题程序员面试题精选100题程序员面试题精选100题程序员面试题精选100题程序员面试题精选100题程序员面试题精选100题程序员面试题精选100题程序员面试题精选100题程序员面试...
前端程序员面试分类模拟题--附答案详解
程序员入职的必经之路,面试官面前的证书,成功的基础从这里开始
黑马程序员 - Java基础教学 - 04 - 数组、进制转换、二维数组
Java程序员面试题集(1-50),共50道题目,都是面试java程序员必备的题目,有答案和详细解释
程序员面试宝典-前端-2023最新版 包括“面试涉及范围”、“岗位技能要求” 从“素质考察”、“项目经验考察”、“技能考察”三个方面入手,题目由浅入深、前后关联、多数题目没有标准的答案,主要对技术深度挖掘及...
程序员面试题精选程序员面试题精选程序员面试题精选
程序员面试宝典 第5版-欧立奇.part2.rar
本人费尽大力气一条一条收集的程序员面试题精选(1-57)。里面包含了各种数据结构的经典算法,非常值得一做。
程序员面试题精选 C++ 算法 微软 google 程序员面试题精选 C++ 算法 微软 google