2 mrguanb MrGuanB 于 2015.06.02 16:38 提问

求教一个百度面试的算法题

一个有N个元素的一维数组(A[0],A[1], ..., A[n-1]),设计一个算法求解该数组最大子数组。(要求时间复杂度是O(n))

3个回答

caozhy
caozhy   Ds   Rxr 2015.06.02 18:26
caozhy
caozhy   Ds   Rxr 2015.06.02 18:26
houoyufeng
houoyufeng   2015.06.02 19:55

哈,这道题啊,已经遇到好多次了,推荐一个很多人都在练习的网站,leetcode,这上面差不多都是这种题。
这个题思想是动态规划,而且是简单的dp。每次都统计之前的累计和,累计和小于0时就找到一个子序列,看看是不是最大的,后面继续扫描。

Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
2018年百度Java后端面试题算法题
1、给一个函数,返回0和1,概率为p和1-p,请你实现一个函数,使得返回0、1的概率一样分析:这是典型的随机概率发生器的案例,我们先用数学知识来分析一下,函数返回0出现的概率为p,返回1出现的概率为1-p,如果单独返回1位0或1位1,那么没有办法实现返回0和1的概率一样。所以我们需要更大的位数来分析,因为存在返回0和1两种情况,我们把位数定为2,那么组合出来的信息就有2*2=4种:00 ---&g...
算法与数据结构——百度笔试题(一)
算法题 6:任意数分三组,使得每组的和尽量相等(百度面试题) 题目:任意数分三组,使得每组的和尽量相等 ************************************************************************************************************************************** 算法题 18
百度面试算法题
在一组排序数中,给定一个数,返回最接近且不大于这个数的位置,要求时间在O(logn) 用二分查找,low和high相差为1时,low即为所求结果的下标。static int BSearch(int[] num, int key) { if(key>num[num.length-1]){ return num[num.length-1]; }
测试开发面试真题—算法(百度)
1、请列举常用的算法,并说明其时间复杂读,并说明排序思想? ①冒泡排序:量量比较待排序数据元素的大小,发现两个数据元素的次序相反时进行交换,直到没有反序的数据元素为止。时间复杂度是O(n*2)。稳定的。 public class bubble1 { public static void main(String[] args) { int[] array = { 7, 8, 3, 1,
算法题 90:从多个数组中找最大值(百度笔试题
题目:有n个长度均为m的整型数组,数组中的元素都是从小到大有序排列,从所有这些数组m*n个数中,找出值最大的前k个。请给出思路和时间复杂度。 类似赛马问题做法 本Markdown编辑器使用StackEdit修改而来,用它写博客,将会带来全新的体验哦: Markdown和扩展Markdown简洁的语法 代码块高亮 图片链接和图片上传 LaTex数学公式 UML序列图和流程图 离线写博客 导入...
中文分词算法-百度面试题
题目: 给定一个字符串, 一个数组,判断这个字符串能否被分隔成字典里的一个个单词。用动态规划算法 我面试时写的是下面的代码 public static boolean divied2(String s,String[] dict){ boolean result=false; if(s.length()==0) return true
2017百度面试现场coding算法一
求字符串中字符的出现次数,并按照字典序排列 输入:“I am a student a boy” 输出:[(I,1),(a,2),(am,1),(boy,1),(student,1)] (注意字符串截取的规则,注意最后单词的处理,注意比较函数的引用)struct Item{ string word; int count; }; bool compare(Item &a,Item
深度学习算法工程师笔试题(百度)
百度2013深度学习算法工程师笔试题。
百度的android面试总结分析
今天就是今天上午10点,我接到了百度的电话面试,当然提前和我说了,我的拖延症是有多强烈,以至于我没怎么准备,当然我也想着看看自己的真实水平,在此检讨一下!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!废话不多说上来就是百度的一个技术人员打过电话来,简单确认了我的信息之后,就开始问问题,此刻我的心中有一万匹草泥马奔腾。。。。
百度测试开发面试题
学姐、学长总结的面试题  感谢学姐(针对质量部测试开发) 1.几种常见算法看下,能够大概描述出来算法的过程,复杂度(排序、查找等) 2.给你设定几种场景,让你解答:比如给你两部手机,让你站在一百层楼高的地方,假设在第n层手机摔下就会摔破,问你怎样用着两部手机确定这个临界层。 (场景测试-百度质量部) 3.怎样知道一个链表里是否有环的存在,以及确定环的位置  如何确定两个链表