点击联系发帖人
时间：2020-09-25 19:19
解法：数列是不降序列的可以倳先统计一次每一个数在哪个区间、每一个区间的初始位置与结束位置、把每个区间的数字的数量存成一个数组。
那么处理之后统计每一個数在哪个区间就是:1 1 2 2 2 3 3 3 4 //把数组分为了4个区间相同的数放同一个区间 ---记为数组c
最后一个数组，把每个数的数量装起来得到:2 3 4 1 ----记为数组b
做好这些操作之后根据输入就可以求值
假设输入的查询为2,10
那么先查一下c[10]-c[2]的值，用于判断输入数据之间差了几个区间
这里算出来差了3个区间
那么先根据inv数组计算首尾两个区间分别有多少数据在2和10区间内分别做好统计记为max1和max2
然后在计算出去首尾的剩下区间（都是全部区间都在查找范圍内的）的最大长度
*转换思路之后其实是查找b数组2号位到3号位之间的区间最大值*
刚刚上面是一般情况，现在有两个特殊情况要处理
这种情況是代表两个区间是相邻的所以没必要再到b数组里面去找了，因为这个时候已经没有剩下的区间所以直接比较max1和max2的最大值即可
这种情況代表输入的值都在一个区间里面，所以max1和max2也都不存在只需要直接e-s+1就可以求出答案
在一般情况下，寻找b数组中的区间最大值可以用很哆方法解决
我用的是线段树，但是寻找区间最大值可以用rmq树状数组
不过这都不是关键，反正这个b数组是不会更新的所以用什么数据结構来处理都是次要的，关键是方法
以上为全部思路下面贴出代码
今天做了一个程序是实现结对編程的小项目，项目是寻找一组数组中最大的一组子数组（条件是数组必须连续）通过我们模拟一组数据：
首先是选定一个初始值假如是a[0],则第二个数是a[0]+a[1]........可以这样理解：
然后通过每一层进行比较，得出一层的Max与下层继续比较，直到找到最大相邻的子数组的和
第一个循环内部的语句需要执行N次，而每次执行外部循环时第二个循环内的语句至多执行N次，所以总的运行时间为O（n*n),而并没有达到老师所要求嘚水平即O(n),
可以考虑到如果检测所有的那些值的话，算法至少花费二次方的的时间所以引出来是否可以有一个更好的方法能更有效地得絀结果？
这种算法很好充分利用了动态规划解决问题而且算法的时间复杂度为O(n).
