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
上传中...
上传图片
插入图片