网页
资讯
视频
图片
知道
文库
贴吧
地图
采购
进入贴吧
全吧搜索
吧内搜索
搜贴
搜人
进吧
搜标签
日
一
二
三
四
五
六
签到排名:今日本吧第
个签到,
本吧因你更精彩,明天继续来努力!
本吧签到人数:0
一键签到
成为超级会员,使用一键签到
一键签到
本月漏签
0
次!
0
成为超级会员,赠送8张补签卡
如何使用?
点击日历上漏签日期,即可进行
补签
。
连续签到:
天 累计签到:
天
0
超级会员单次开通12个月以上,赠送连续签到卡3张
使用连续签到卡
10月02日
漏签
0
天
算法吧
关注:
30,420
贴子:
59,085
看贴
图片
吧主推荐
视频
游戏
5
回复贴,共
1
页
<<返回算法吧
>0< 加载中...
求一个最长的,元素和为非负的子数组。
只看楼主
收藏
回复
K_I_T_T
蔡基
3
该楼层疑似违规已被系统折叠
隐藏此楼
查看此楼
【注意:不是求元素和最大的子数组】
如果用O(n^2)的时间太容易了,想问诸位大神,有没有比O(n^2)更快的算法呢?
我尝试了几种O(n)的算法,不过发现结果都是不对的。在这里给出几个数组的例子,以检测算法是否正确:
举例A:{1, 2, -4, 5, -6, 7}。最长的和为非负的子数组应该是其本身。长度为6,和为5.
举例B:{1, 1, 1, 1, -4, -4, 3}。最长的和为非负的子数组应该是B[0..4],和为0。
光之寒月
新人王
8
该楼层疑似违规已被系统折叠
隐藏此楼
查看此楼
最简单的就是数据结构优化:
在前缀和上建区间数据结构(比如动态权值线段树或前缀和离散化后建普通权值线段树,平衡树也可以)加速成O(nlogn)
node[i]记录前缀和为i的最小下标,查询区间最大值可以logn获得一个点作为右端点时的最长长度
北京简单科技有限公司
高中数学
算法
初步视频新学期计划学——预约每天学习章节——定时学习——快速答疑高中数学
算法
初步视频注册简单一百,免费领取初初中各科视频资源,新学期不用愁!
2024-10-02 14:26
广告
立即查看
3215469780
老湿
12
该楼层疑似违规已被系统折叠
隐藏此楼
查看此楼
亦如,流水,一去不返。不泣离别,不诉终殇。
登录百度账号
扫二维码下载贴吧客户端
下载贴吧APP
看高清直播、视频!
贴吧页面意见反馈
违规贴吧举报反馈通道
贴吧违规信息处理公示