r**u
发帖数: 1567 | 1 Given an array, find the longest subarray which the sum of the subarray less
or equal then the given MaxSum.
int[] FindMaxSumArray(int[] array, int maxsum)
for example, given array: {1, -2, 4, 5, -2, 6, 7}
maxsum=7
the result would be: {1,-2, 4, -2, 6} |
g*******y
发帖数: 1930 | 2 看例子，难道不要求连续？？？
那有啥难度？直接sort不就完了。
less
【在 r**u 的大作中提到】
: Given an array, find the longest subarray which the sum of the subarray less
: or equal then the given MaxSum.
: int[] FindMaxSumArray(int[] array, int maxsum)
: for example, given array: {1, -2, 4, 5, -2, 6, 7}
: maxsum=7
: the result would be: {1,-2, 4, -2, 6}
|
j*a
发帖数: 14423 | 3 lol. good one.
【在 g*******y 的大作中提到】
: 看例子，难道不要求连续？？？
: 那有啥难度？直接sort不就完了。
:
: less
|
r**u
发帖数: 1567 | 4 可以不连续。不明白sort完了怎么办？
【在 g*******y 的大作中提到】
: 看例子，难道不要求连续？？？
: 那有啥难度？直接sort不就完了。
:
: less
|
m*****f
发帖数: 1243 | 5 哎， 从最小的开始加...
【在 r**u 的大作中提到】
: 可以不连续。不明白sort完了怎么办？
|
H*M
发帖数: 1268 | 6 ?
The result is not correct
should be [-2 -2 1 6] or [-2 -2 1 4] or [-2 -2 1 5]
If only [-2 -2 1 4] is expected, yeah, we can sort it and add from the small
est;
but if [-2 -2 1 6] is expected, some tricks need to be applied...
less
【在 r**u 的大作中提到】
: Given an array, find the longest subarray which the sum of the subarray less
: or equal then the given MaxSum.
: int[] FindMaxSumArray(int[] array, int maxsum)
: for example, given array: {1, -2, 4, 5, -2, 6, 7}
: maxsum=7
: the result would be: {1,-2, 4, -2, 6}
|
a********a
发帖数: 219 | 7 你的头像比你的答案好看。
【在 m*****f 的大作中提到】
: 哎， 从最小的开始加...
|
t********e
发帖数: 25 | |
o********r
发帖数: 79 | 9 他的结果才是longest吧。你的不对。
small
【在 H*M 的大作中提到】
: ?
: The result is not correct
: should be [-2 -2 1 6] or [-2 -2 1 4] or [-2 -2 1 5]
: If only [-2 -2 1 4] is expected, yeah, we can sort it and add from the small
: est;
: but if [-2 -2 1 6] is expected, some tricks need to be applied...
:
: less
|
o********r
发帖数: 79 | 10 同问。
【在 g*******y 的大作中提到】
: 看例子，难道不要求连续？？？
: 那有啥难度？直接sort不就完了。
:
: less
|
|
|
H*M
发帖数: 1268 | 11 又看错了.没睡醒还......
【在 o********r 的大作中提到】
: 他的结果才是longest吧。你的不对。
:
: small
|
m*****f
发帖数: 1243 | 12 那比我头像好看的答案是什么?
【在 a********a 的大作中提到】
: 你的头像比你的答案好看。
|
H*M
发帖数: 1268 | 13 你男的女的?
【在 m*****f 的大作中提到】
: 那比我头像好看的答案是什么?
|
k***e
发帖数: 556 | 14 如果要求连续好像就很难了。
还没想出怎么做。
【在 g*******y 的大作中提到】
: 看例子，难道不要求连续？？？
: 那有啥难度？直接sort不就完了。
:
: less
|
l*y
发帖数: 21010 | 15 用dynamic programming
随便找本算法书应该有
【在 k***e 的大作中提到】
: 如果要求连续好像就很难了。
: 还没想出怎么做。
|
k***e
发帖数: 556 | 16 你是不是搞错题目了
这里有一个upper bound的要求，不是求最大连续和
【在 l*y 的大作中提到】
: 用dynamic programming
: 随便找本算法书应该有
|
k***e
发帖数: 556 | 17 在n＊n就可以可以就解 因为只要check 所以的a[i:j], then take the longest
however, how to do better than n^2
用D
【在 H*M 的大作中提到】
: 你男的女的?
|
g*******y
发帖数: 1930 | 18 我觉得如果要求连续，能找到nlogn的算法，再怎么进一步优化就没想到了。
【在 k***e 的大作中提到】
: 如果要求连续好像就很难了。
: 还没想出怎么做。
|
k***e
发帖数: 556 | 19 did you use divide and conqure and also use continuous sum ending at
a position which is min as a subroutine?
【在 g*******y 的大作中提到】
: 我觉得如果要求连续，能找到nlogn的算法，再怎么进一步优化就没想到了。
|
g*******y
发帖数: 1930 | 20 Divide and conquer works? The "conqure" step takes O(n)? how?
我的想法是:
1. 转化为一个等价问题：
sum' = total sum - target_max_sum
问题转化为：在数组中找两段子数组，一段A数组从头开始，一段B数组在尾巴结束，这
两个数组之和>=sum'，这两个数组的元素个数之和最小
2. sumA[i]= a[0] + ... + a[i],
sumB[i] = total sum - sumA[i-1] ...
3. define一个map mA, mB; 然后：
mA.insert(make_pair(sumA[i] ,i+1));
mB.insert(make_pair(sumB[i] ,N-i));
这一步要O(nlogn), 因为map是要对key排序的。
4. 把map中的value值改变为:
mA[key] = min{k+1}, for all sum[k] >= key,
这一步只要O(n)，因为mA已经是按key排好序的;
现在这个mA中每一项的含义就是：
【在 k***e 的大作中提到】
: did you use divide and conqure and also use continuous sum ending at
: a position which is min as a subroutine?
|
|
|
r********t
发帖数: 395 | 21
less
可以参照这个算法：
http://en.wikipedia.org/wiki/Maximum_subarray_problem
【在 r**u 的大作中提到】
: Given an array, find the longest subarray which the sum of the subarray less
: or equal then the given MaxSum.
: int[] FindMaxSumArray(int[] array, int maxsum)
: for example, given array: {1, -2, 4, 5, -2, 6, 7}
: maxsum=7
: the result would be: {1,-2, 4, -2, 6}
|
g*******y
发帖数: 1930 | 22 你贴的max sum问题，跟这个题还是有很大的不同吧
【在 r********t 的大作中提到】
:
: less
: 可以参照这个算法：
: http://en.wikipedia.org/wiki/Maximum_subarray_problem
|
k***e
发帖数: 556 | 23 I just doubt whether step 4 can be done in nlogn
it is true that the key are sorted. however, the idx corresponds to the key
has no order. Thus you may need to take linear time to find the
corresponding min idx.
I thought I get the nlogn and later found it is wrong ... |
g*******y
发帖数: 1930 | 24 第4步，
map::iterator iter=m.begin()
map::iterator iternext=m.begin(); iternext++;
for(;iternext!=m.end();iter++,iternext++){
iternext->second = MIN(iternext->second, iter->second);
}
值得考虑的是stl里面map的iterator是不是可以做到线性时间的遍历，如果不是就只有
自己写了。自己写是肯定可以做到的，就是一个带prev, next的BST，或者说就是一个
树和链表的结合。
key
【在 k***e 的大作中提到】
: I just doubt whether step 4 can be done in nlogn
: it is true that the key are sorted. however, the idx corresponds to the key
: has no order. Thus you may need to take linear time to find the
: corresponding min idx.
: I thought I get the nlogn and later found it is wrong ...
|
b***e
发帖数: 1419 | 25 恕我眼拙, 这个难道不是背包问题么?
less
【在 r**u 的大作中提到】
: Given an array, find the longest subarray which the sum of the subarray less
: or equal then the given MaxSum.
: int[] FindMaxSumArray(int[] array, int maxsum)
: for example, given array: {1, -2, 4, 5, -2, 6, 7}
: maxsum=7
: the result would be: {1,-2, 4, -2, 6}
|
b****j
发帖数: 78 | 26 有负数的
【在 b***e 的大作中提到】
: 恕我眼拙, 这个难道不是背包问题么?
:
: less
|
b***e
发帖数: 1419 | 27 说的就是。这个比背包还难，那还真的是难一点的题。
【在 b****j 的大作中提到】
: 有负数的
|
g*******y
发帖数: 1930 | 28 如果题目要求子数组是可以不连续的subsequence，sort一遍从最小的开始求和就是一
个贪心解吧。
如果要求必须是连续的子数组，至少有nlogn的解(我前面贴的，我实现了一下，应该没
啥问题)
【在 b***e 的大作中提到】
: 说的就是。这个比背包还难，那还真的是难一点的题。
|
