自己想了一道连续数组变形题 解不出来 求分享下思路

pandami 发表于 2021-2-25 06:24
递增数组是按照presum排序吗？
如果这样，第一个大于的不一定是序号最小的
因为有负数

类似于单调队列，你要扔掉一些对答案没有贡献的elements
用楼主的例子：
[1,3,-5,6,0,2,-4,6]
前缀和是
[1,4,-1,5,5,7,3,9]
那么我们单调数组里面存
{(1,1),(4,2),(5,4),(7,6),(9,8)} pair第一数据是值，第二个数据是位置
然后用这个数组的第一数据来二分

cikedewu 发表于 2021-2-25 05:34
先做一个sum array，记录从第一个加到最后一个的sum，然后用两个pointer，left, right，结合之前的sum arra ...

感谢分享 我去做了一下你提供的这道题  是道好题！ （因为我不会做 哈哈哈）  看了下题解之后扩展了思路
862 和我的题很像 但是有一个很重要的关键点  在于862要是的最短的 而我的这个是最长的

我思考了一下 尝试套用类似的模板 使用递减单调栈来做 发现不行

我总结了一下思路 如果想要的是最短子数组， 那么我们会可以使用单调栈来维护最新的元素 舍去老的元素
但是如果要最长子数组的话我们想要留下最老的元素 这样似乎单调栈就不可用了

也许我的思维被局限了 如果有新想法欢迎指教  再次感谢！

油泼扯面加冰峰 发表于 2021-2-25 04:14
前缀和+递增stack 行不行？只是空想了一下，没推演

补充内容 (2021-2-25 04:27):

谢谢分享 不过我顺着楼下的层主分享的题试了一下 感觉不太行

pandami 发表于 2021-2-25 04:03
所以V可以是负数

补充内容 (2021-2-25 04:12):

感谢思路分享  我记得线段树和前缀和在查找上面效率是一样的 只是线段树在更新上效率更高
这道题似乎不需要更新 所以理论上应该不需要线段树
我尝试使用前缀和去解决这个问题但是没有什么思路  楼下我看到了一个二分的思路但是还没来得及思考
先回复你一下哈 再次感谢！

pandami 发表于 2021-2-25 04:03
所以V可以是负数

补充内容 (2021-2-25 04:12):

我看懂5楼的大神讲得线段树和二分的用法了  
我之前理解你说的线段树是用来求和的 原来还可以用来配合前缀和存区间最大值的 又开拓了思路

PandaLeaves 发表于 2021-2-25 05:55
先前缀和。我们用s_i 来表示a_1+a_2...+a_i 的和。然后扫一遍数组，对于每个s_i,我们像找到最小的j, 使得s_ ...

感谢大神！！ 太牛了 讲得也好清楚 学到了好多新思路  太感谢啦！！！ 学到了好多东西  我这就去总结一下
好激动啊  再次感谢大神！！