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

最近刷了好多子数组/子序列， 包含负数不包含负数，子数组和等于/小于target的题
然后我结合了一下各类型的题给自己出了一道变形题 然而并没有好的思路
求大家帮我看一下  有见识的大佬如果发现它是LeetCode原题的话希望可以告诉我

题如下:

给定一个数组nums，里面包含正数和负数， 给定一个目标值V， 求子数组和不大于V的最长子数组长度

例 nums = [1,3,-5,6,0,2,-4,6]  V=6

ans = 7

最长子数组为[1,3,-5,6,0,2,-4]
1+3-5+6+0+2-4 = 3

我挠破头也只能想出O(n^2)的解
但是感觉计算好像是有冗余的 不知道该怎么优化 希望大家提供一下思路 （如果能给个pseudocode就更好了）

感激不尽！

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第一数据是值，第二个数据是位置
然后用这个数组的第一数据来二分

先前缀和。我们用s_i 来表示a_1+a_2...+a_i 的和。然后扫一遍数组，对于每个s_i,我们像找到最小的j, 使得s_i-s_j<=V.
所问题变成了动态询问数组里面第一个大于k的位置，where k=s_i-V.
这个问题可以：

1.直接用线段树来做，每个线段维护区间最大值，然后动态插入。O(n log n)
2. 或者我们可以维护一个单调数组，然后二分来做。O(n log n).

所以V可以是负数

补充内容 (2021-2-25 04:12):
也许用segment tree可以nlogn
因为你需要知道某个index之前某个数据区间对应的最小坐标

前缀和+递增stack 行不行？只是空想了一下，没推演

补充内容 (2021-2-25 04:27):
感觉不太行

先做一个sum array，记录从第一个加到最后一个的sum，然后用两个pointer，left, right，结合之前的sum array来检查当前sub array(left right)是否符合，如果符合直接输出当前长度，如果不是，比较原始数列left 和right 大小，谁大就去掉谁

补充内容 (2021-2-25 05:40):
有bug，不是正解

补充内容 (2021-2-25 05:44):
试试map和heap，参考leetcode 862

PandaLeaves 发表于 2021-02-24 13:55:18
先前缀和，然后问题变成动态询问数组里面第一个小于k的位置。
我们可以维护一个单调数组，然后二分来做。
O(n log n).

如何二分？
单调数组按照什么排序？

pandami 发表于 2021-2-25 05:58
如何二分？
单调数组按照什么排序？

我们注意到在前缀和数组中，如果s_a<s_b且a>b，那么s[a]对于答案没有贡献。
所以我们维护一个严格递增的数组
对于每个i, 我们在那个数组里面找到第一个大于s_i-V的数，得到当前以i结尾的最大长度。

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

666666666

pandami 发表于 2021-2-25 05:58
如何二分？
单调数组按照什么排序？

二分找能满题目要求加和的条件的最小的index， 这样长度最长

PandaLeaves 发表于 2021-02-24 14:06:44
我们注意到在前缀和数组中，如果s_a<s_b且a>b，那么s对于答案没有贡献。
所以我们维护一个严格递增的数组
对于每个i, 我们在那个数组里面找到第一个大于s_i-V的数，得到当前以i结尾的最大

递增数组是按照presum排序吗？
如果这样，第一个大于的不一定是序号最小的
因为有负数