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



