栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

Best cow fences(大于某个长度的最大子序和)

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

Best cow fences(大于某个长度的最大子序和)

首先从最基本的出发;
1.求出一个序列的最大字段和
一个O(N)的做法是从头到尾扫描,并不断用sum里加入这个数,如果段和为负数,那么就重开。
2.求一个长度大于L的最大子段和
这个时候第一个方法肯定不适用了,因为没有规定长度
这个时候用前缀和,复杂度O(n*n);
3.求一个长度大于L的平均数最大的连续子段
这个时候和1,2发生了很大的区别,因为是求的平均数,而不是简简单单求个和
这个时候我们可以用二分法,首先,我们可以求一个长度大于L的最大字段和
,那么不妨假设平均数为A,然后序列全部减去A后得到一个新的序列,这个时候结合2,如果存在长度大于L的最大子段,如果大于0,那么就可以说明这个平均数可以再次扩大,然后最后确定出这个最大的平均数

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/301373.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号