[问一道题] maximum contiguous subarray with sum >= target number# JobHunting - 待字闺中
c*m
1 楼
别人分享的面经里面扩展的题，想不出O(N)的方法。请大牛们指点
j*8
2 楼
这个有啥tricky的地方吗，难道不是加个condition check currSum >= target 就行？
【在 c*****m 的大作中提到】
: 别人分享的面经里面扩展的题，想不出O(N)的方法。请大牛们指点
【在 c*****m 的大作中提到】
: 别人分享的面经里面扩展的题，想不出O(N)的方法。请大牛们指点
c*m
3 楼
curSum < target的时候怎么操作呢？
【在 j*****8 的大作中提到】
: 这个有啥tricky的地方吗，难道不是加个condition check currSum >= target 就行？
【在 j*****8 的大作中提到】
: 这个有啥tricky的地方吗，难道不是加个condition check currSum >= target 就行？
j*8
4 楼
继续加
if currSum < 0 then currSum = 0
else if currSum >= target && currSum > curMax then currMax = currSum
没仔细想，可能不对
【在 c*****m 的大作中提到】
: curSum < target的时候怎么操作呢？
if currSum < 0 then currSum = 0
else if currSum >= target && currSum > curMax then currMax = currSum
没仔细想，可能不对
【在 c*****m 的大作中提到】
: curSum < target的时候怎么操作呢？
c*m
5 楼
没错。我自己把问题想错了，之前脑子里面想的是找出 >= target的所有contiguous
subarray里面长度最大的那个.
【在 j*****8 的大作中提到】
: 继续加
: if currSum < 0 then currSum = 0
: else if currSum >= target && currSum > curMax then currMax = currSum
: 没仔细想，可能不对
subarray里面长度最大的那个.
【在 j*****8 的大作中提到】
: 继续加
: if currSum < 0 then currSum = 0
: else if currSum >= target && currSum > curMax then currMax = currSum
: 没仔细想，可能不对
j*8
6 楼
那个也一样吧，只是不记录currMaxSum，而是currMaxLength
contiguous
【在 c*****m 的大作中提到】
: 没错。我自己把问题想错了，之前脑子里面想的是找出 >= target的所有contiguous
: subarray里面长度最大的那个.
contiguous
【在 c*****m 的大作中提到】
: 没错。我自己把问题想错了，之前脑子里面想的是找出 >= target的所有contiguous
: subarray里面长度最大的那个.
c*m
7 楼
这种情况的话，在curSum < target时，不能把curSum重置０吧？比如target = 10,
array=[-1, 100]，最大长度是２，而不是１
【在 j*****8 的大作中提到】
: 那个也一样吧，只是不记录currMaxSum，而是currMaxLength
:
: contiguous
array=[-1, 100]，最大长度是２，而不是１
【在 j*****8 的大作中提到】
: 那个也一样吧，只是不记录currMaxSum，而是currMaxLength
:
: contiguous
j*8
8 楼
en，你是对的
那就得用求subarray sum来做了
【在 c*****m 的大作中提到】
: 这种情况的话，在curSum < target时，不能把curSum重置０吧？比如target = 10,
: array=[-1, 100]，最大长度是２，而不是１
那就得用求subarray sum来做了
【在 c*****m 的大作中提到】
: 这种情况的话，在curSum < target时，不能把curSum重置０吧？比如target = 10,
: array=[-1, 100]，最大长度是２，而不是１
c*m
9 楼
和暴力的方法的复杂度都是O(N^2)的吧？
【在 j*****8 的大作中提到】
: en，你是对的
: 那就得用求subarray sum来做了
【在 j*****8 的大作中提到】
: en，你是对的
: 那就得用求subarray sum来做了
j*8
10 楼
好像是。。
【在 c*****m 的大作中提到】
: 和暴力的方法的复杂度都是O(N^2)的吧？
【在 c*****m 的大作中提到】
: 和暴力的方法的复杂度都是O(N^2)的吧？
r*g
11 楼
https://en.wikipedia.org/wiki/Maximum_subarray_problem
【在 c*****m 的大作中提到】
: 别人分享的面经里面扩展的题，想不出O(N)的方法。请大牛们指点
【在 c*****m 的大作中提到】
: 别人分享的面经里面扩展的题，想不出O(N)的方法。请大牛们指点
b*n
12 楼
如果是求最长的subarray的话，用TreeMap可以O(nlogn)，
谨慎地认为没有更好的解了。。
谨慎地认为没有更好的解了。。
i*l
13 楼
我想到了一个办法，刚刚试了一下，确实是O(N)的。
思路就是从两头往中间凑，先得到全部的和，如果满足条件就返回了，
如果不满足，比较两头的大小，每次减去小的那个，然后走一步，代码如下：
int maxSubLen( vector& data, int bar ) {
int sz = data.size(), sum = 0;
for( int i=0; i
int i = 0, j = sz-1;
while( i < j ) {
if( data[i] < data[j] ) sum -= data[i++];
else sum -= data[j--];
if( sum >= bar ) return j - i + 1;
}
return 0;
}
int main() {
vector v {-1,-1,-1,2,-1,-1,100};
vector v2 {1,-1,-1,1,-1,-1,1,-1,-2,7};
vector v3 {-1,-1,-1,2,-1,-1,1};
cout<
都在刷题奋力找工作中，共勉
【在 c*****m 的大作中提到】
: 别人分享的面经里面扩展的题，想不出O(N)的方法。请大牛们指点
思路就是从两头往中间凑，先得到全部的和，如果满足条件就返回了，
如果不满足，比较两头的大小，每次减去小的那个，然后走一步，代码如下：
int maxSubLen( vector
int sz = data.size(), sum = 0;
for( int i=0; i
int i = 0, j = sz-1;
while( i < j ) {
if( data[i] < data[j] ) sum -= data[i++];
else sum -= data[j--];
if( sum >= bar ) return j - i + 1;
}
return 0;
}
int main() {
vector
vector
vector
cout<
都在刷题奋力找工作中，共勉
【在 c*****m 的大作中提到】
: 别人分享的面经里面扩展的题，想不出O(N)的方法。请大牛们指点
a*g
14 楼
有个反例子：｛1，1，1，1，1，-9，7｝，target:5
正确的答案是1，1，1，1，1长度是5
而你的解法的答案是7，长度只有1
【在 i******l 的大作中提到】
: 我想到了一个办法，刚刚试了一下，确实是O(N)的。
: 思路就是从两头往中间凑，先得到全部的和，如果满足条件就返回了，
: 如果不满足，比较两头的大小，每次减去小的那个，然后走一步，代码如下：
: int maxSubLen( vector& data, int bar ) {
: int sz = data.size(), sum = 0;
: for( int i=0; i
:
: int i = 0, j = sz-1;
: while( i < j ) {
正确的答案是1，1，1，1，1长度是5
而你的解法的答案是7，长度只有1
【在 i******l 的大作中提到】
: 我想到了一个办法，刚刚试了一下，确实是O(N)的。
: 思路就是从两头往中间凑，先得到全部的和，如果满足条件就返回了，
: 如果不满足，比较两头的大小，每次减去小的那个，然后走一步，代码如下：
: int maxSubLen( vector
: int sz = data.size(), sum = 0;
: for( int i=0; i
:
: int i = 0, j = sz-1;
: while( i < j ) {
y*e
15 楼
如果array里面每一个数字都是正的话，那么有最优解时间O(N)，空间O(1)。用一个
slicing window就好。
若是有负的数字，没有O(N)时间的解答，最好的是O(NlogN)。
【在 c*****m 的大作中提到】
: 别人分享的面经里面扩展的题，想不出O(N)的方法。请大牛们指点
slicing window就好。
若是有负的数字，没有O(N)时间的解答，最好的是O(NlogN)。
【在 c*****m 的大作中提到】
: 别人分享的面经里面扩展的题，想不出O(N)的方法。请大牛们指点
b*n
16 楼
又想了一下，其实是有O(N)的解的。
先precompute sum array，b[x] = sum(a[0] + a[1] + ... + a[x])
然后问题相当于在b里面找两个个index i，j, i在左边j在右边， b[j] - b[i] >= tar
，并且要j - i的值最大。
所有可能作为i的candidate实际上只有从b[0]开始向右的严格递减subsequence，
因为假如x > y并且b[x] > b[y]的话，那么x不可能作为i，因为y作为i更好。
同样，所有可能作为j的candidate实际上只有从b[n]开始向左的严格递增subsequence。
举个例子，如果b = [5, 4, 2, 8, 3, 7]
那么i的可能其实只有index 0,1,2,
j的可能其实只有index 3,5
然后用两个pointer分别从这两个序列的尾部开始往前移动就可以了，时间复杂度整体
上是O(N)因为上面每一步都是O(N)
【在 y*********e 的大作中提到】
: 如果array里面每一个数字都是正的话，那么有最优解时间O(N)，空间O(1)。用一个
: slicing window就好。
: 若是有负的数字，没有O(N)时间的解答，最好的是O(NlogN)。
先precompute sum array，b[x] = sum(a[0] + a[1] + ... + a[x])
然后问题相当于在b里面找两个个index i，j, i在左边j在右边， b[j] - b[i] >= tar
，并且要j - i的值最大。
所有可能作为i的candidate实际上只有从b[0]开始向右的严格递减subsequence，
因为假如x > y并且b[x] > b[y]的话，那么x不可能作为i，因为y作为i更好。
同样，所有可能作为j的candidate实际上只有从b[n]开始向左的严格递增subsequence。
举个例子，如果b = [5, 4, 2, 8, 3, 7]
那么i的可能其实只有index 0,1,2,
j的可能其实只有index 3,5
然后用两个pointer分别从这两个序列的尾部开始往前移动就可以了，时间复杂度整体
上是O(N)因为上面每一步都是O(N)
【在 y*********e 的大作中提到】
: 如果array里面每一个数字都是正的话，那么有最优解时间O(N)，空间O(1)。用一个
: slicing window就好。
: 若是有负的数字，没有O(N)时间的解答，最好的是O(NlogN)。
y*e
17 楼
tar
subsequence。
举个例子：b = [1, 5, 9, 4, 2, 8, 3, 7, 9]
按照你的算法，如何求 i 和 j 呢？
【在 b*****n 的大作中提到】
: 又想了一下，其实是有O(N)的解的。
: 先precompute sum array，b[x] = sum(a[0] + a[1] + ... + a[x])
: 然后问题相当于在b里面找两个个index i，j, i在左边j在右边， b[j] - b[i] >= tar
: ，并且要j - i的值最大。
: 所有可能作为i的candidate实际上只有从b[0]开始向右的严格递减subsequence，
: 因为假如x > y并且b[x] > b[y]的话，那么x不可能作为i，因为y作为i更好。
: 同样，所有可能作为j的candidate实际上只有从b[n]开始向左的严格递增subsequence。
: 举个例子，如果b = [5, 4, 2, 8, 3, 7]
: 那么i的可能其实只有index 0,1,2,
: j的可能其实只有index 3,5
b*n
18 楼
这种情况下i只可能是0，因为后面没有比1小的了
j只可能是8，因为前面没有比9大的了
这个array里面没有比9-1更好也更长的b[j] - b[i]了
j只可能是8，因为前面没有比9大的了
这个array里面没有比9-1更好也更长的b[j] - b[i]了
j*8
19 楼
但如果当前 i, j 不满足条件并且 i 向右 j 向左 都可以时，先移动哪一个？
我把你的例子b稍微改了下 b = [6, 5,4,10,3,7], target = 4
i 还是可选 0,1,2；j 还是可选3，5
i = 0, j = 5 时不满足条件，这个时候先移 i 还是 j？ 感觉按你的算法应该先移 i
， 但那样就拿不到 i = 0 j = 3 的解了？
tar
subsequence。
【在 b*****n 的大作中提到】
: 又想了一下，其实是有O(N)的解的。
: 先precompute sum array，b[x] = sum(a[0] + a[1] + ... + a[x])
: 然后问题相当于在b里面找两个个index i，j, i在左边j在右边， b[j] - b[i] >= tar
: ，并且要j - i的值最大。
: 所有可能作为i的candidate实际上只有从b[0]开始向右的严格递减subsequence，
: 因为假如x > y并且b[x] > b[y]的话，那么x不可能作为i，因为y作为i更好。
: 同样，所有可能作为j的candidate实际上只有从b[n]开始向左的严格递增subsequence。
: 举个例子，如果b = [5, 4, 2, 8, 3, 7]
: 那么i的可能其实只有index 0,1,2,
: j的可能其实只有index 3,5
我把你的例子b稍微改了下 b = [6, 5,4,10,3,7], target = 4
i 还是可选 0,1,2；j 还是可选3，5
i = 0, j = 5 时不满足条件，这个时候先移 i 还是 j？ 感觉按你的算法应该先移 i
， 但那样就拿不到 i = 0 j = 3 的解了？
tar
subsequence。
【在 b*****n 的大作中提到】
: 又想了一下，其实是有O(N)的解的。
: 先precompute sum array，b[x] = sum(a[0] + a[1] + ... + a[x])
: 然后问题相当于在b里面找两个个index i，j, i在左边j在右边， b[j] - b[i] >= tar
: ，并且要j - i的值最大。
: 所有可能作为i的candidate实际上只有从b[0]开始向右的严格递减subsequence，
: 因为假如x > y并且b[x] > b[y]的话，那么x不可能作为i，因为y作为i更好。
: 同样，所有可能作为j的candidate实际上只有从b[n]开始向左的严格递增subsequence。
: 举个例子，如果b = [5, 4, 2, 8, 3, 7]
: 那么i的可能其实只有index 0,1,2,
: j的可能其实只有index 3,5
b*n
20 楼
这个例子里面
i可以选 0，1，2，4
j可以选3，5
i和j都应该从最右边，也就是最大的index开始往左边走，跟sliding window的思路类
似，i开始是4，j开始是5，如果发现a[j] - a[i] >= tar就移动i，反之移动j，相当于
对每个可能的j求最小的i是多少
i
【在 j*****8 的大作中提到】
: 但如果当前 i, j 不满足条件并且 i 向右 j 向左 都可以时，先移动哪一个？
: 我把你的例子b稍微改了下 b = [6, 5,4,10,3,7], target = 4
: i 还是可选 0,1,2；j 还是可选3，5
: i = 0, j = 5 时不满足条件，这个时候先移 i 还是 j？ 感觉按你的算法应该先移 i
: ， 但那样就拿不到 i = 0 j = 3 的解了？
:
: tar
: subsequence。
i可以选 0，1，2，4
j可以选3，5
i和j都应该从最右边，也就是最大的index开始往左边走，跟sliding window的思路类
似，i开始是4，j开始是5，如果发现a[j] - a[i] >= tar就移动i，反之移动j，相当于
对每个可能的j求最小的i是多少
i
【在 j*****8 的大作中提到】
: 但如果当前 i, j 不满足条件并且 i 向右 j 向左 都可以时，先移动哪一个？
: 我把你的例子b稍微改了下 b = [6, 5,4,10,3,7], target = 4
: i 还是可选 0,1,2；j 还是可选3，5
: i = 0, j = 5 时不满足条件，这个时候先移 i 还是 j？ 感觉按你的算法应该先移 i
: ， 但那样就拿不到 i = 0 j = 3 的解了？
:
: tar
: subsequence。
j*8
21 楼
~~~~~~~~~~~~~~~~~~~~~
那时间复杂度就不是线性的了。可能都从右开始能解
决这个例子，但我总觉得还会有别的反例，虽然现在没想出来。。
【在 b*****n 的大作中提到】
: 这个例子里面
: i可以选 0，1，2，4
: j可以选3，5
: i和j都应该从最右边，也就是最大的index开始往左边走，跟sliding window的思路类
: 似，i开始是4，j开始是5，如果发现a[j] - a[i] >= tar就移动i，反之移动j，相当于
: 对每个可能的j求最小的i是多少
:
: i
b*n
22 楼
仍然是线性的，i和j都最多有n个，每一步要么i往坐移要么j往坐移，最多O(2n)。
反例应该是没有的，利用的就是两个sequence其实都是从左往右递增的序列。
【在 j*****8 的大作中提到】
:
: ~~~~~~~~~~~~~~~~~~~~~
: 那时间复杂度就不是线性的了。可能都从右开始能解
: 决这个例子，但我总觉得还会有别的反例，虽然现在没想出来。。
反例应该是没有的，利用的就是两个sequence其实都是从左往右递增的序列。
【在 j*****8 的大作中提到】
:
: ~~~~~~~~~~~~~~~~~~~~~
: 那时间复杂度就不是线性的了。可能都从右开始能解
: 决这个例子，但我总觉得还会有别的反例，虽然现在没想出来。。
r*7
23 楼
这个不是lc上的原题么？
【在 c*****m 的大作中提到】
: 别人分享的面经里面扩展的题，想不出O(N)的方法。请大牛们指点
【在 c*****m 的大作中提到】
: 别人分享的面经里面扩展的题，想不出O(N)的方法。请大牛们指点
b*e
24 楼
我认为是有O(n)的解的。
第一步，先计算从所有位置开始的max sum。这是标准的dp解法。记这个结果array为M[
i]。
第二步，找到从左往右第一个i，使得M[i] >= target。
第三步，从i开始从左往右找第一个j，使得sum[i..j] >= target，并且sum[i..j] + M
[j+1] < target。这是找到了从左往右第一个最长的合法子序列。
第四步，向右挪i，直到(a) i >= j或者(b)sum[i..j] + M[j+1] >= target。如果(a)
发生了，goto第二步。如果(a)没发生但是(b)发生了，goto第三步。
算法描述不是结构化的。但是应该是O(n)的。因为i和j都是从左往右扫描了一遍。
【在 y*********e 的大作中提到】
: 如果array里面每一个数字都是正的话，那么有最优解时间O(N)，空间O(1)。用一个
: slicing window就好。
: 若是有负的数字，没有O(N)时间的解答，最好的是O(NlogN)。
第一步，先计算从所有位置开始的max sum。这是标准的dp解法。记这个结果array为M[
i]。
第二步，找到从左往右第一个i，使得M[i] >= target。
第三步，从i开始从左往右找第一个j，使得sum[i..j] >= target，并且sum[i..j] + M
[j+1] < target。这是找到了从左往右第一个最长的合法子序列。
第四步，向右挪i，直到(a) i >= j或者(b)sum[i..j] + M[j+1] >= target。如果(a)
发生了，goto第二步。如果(a)没发生但是(b)发生了，goto第三步。
算法描述不是结构化的。但是应该是O(n)的。因为i和j都是从左往右扫描了一遍。
【在 y*********e 的大作中提到】
: 如果array里面每一个数字都是正的话，那么有最优解时间O(N)，空间O(1)。用一个
: slicing window就好。
: 若是有负的数字，没有O(N)时间的解答，最好的是O(NlogN)。
相关阅读
要培训一到2个月得icc有人去过么？情况如何stanford cs/ee graduates salary电面结束了，有被欺骗的感觉。同时求助----我现在的情况怎么办？请问relocation里taxable的部分是什么意思？looking for java developer with >5 years experiences (转载)brainbench值得花钱买题做吗？qualcomm等VP approval一周H1B[合集] 这几个offer怎么选？终于等到offer啦拿到小公司offer，人在国内，公司同意给办H1，但要我自己来办新单位报到电面结束，求祝福local小公司面试，什么衣服合适？用FULL TIME OFFER 可以办CPT么？一本用Java进行算法面试的好书团结起来，消灭阿三求问onsite的时间问题。关于一个面试的问题C++ Q96: function inheritance