Z*****Z
发帖数: 723 | 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, -2, 6, 7}
maxsum=7
the result would be: {1,-2, 4, -2, 6}
感觉用两个指针一前一后扫一遍数组就行了？求证。。。
出处：
http://www.mitbbs.com/bbsann2/life.faq/JobHunting/17/D128425435
2821_2.C0/%C0%B4%B5%C0%C4%D1%D2%BB%B5%E3%B5%C4%CC%E2 | p*****2
发帖数: 21240 | | h****e
发帖数: 928 | 3 你觉得可以给出线性的解法？数字可正可负的话，我觉得DP都
不一定能给得出正解。
less
【在 Z*****Z 的大作中提到】
: 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, -2, 6, 7}
: maxsum=7
: the result would be: {1,-2, 4, -2, 6}
: 感觉用两个指针一前一后扫一遍数组就行了？求证。。。
: 出处：
: http://www.mitbbs.com/bbsann2/life.faq/JobHunting/17/D128425435
: 2821_2.C0/%C0%B4%B5%C0%C4%D1%D2%BB%B5%E3%B5%C4%CC%E2
| B*******1
发帖数: 2454 | | h****e
发帖数: 928 | 5 那个O(N)解法看来不行，甚至不能扩展到求最长子数列和为定值的
题目，尤其是有零和负数的时候，例如给定数列{1,1,1,1,-1}
和定值3。
【在 B*******1 的大作中提到】
: 是不是可以用这里的方法？
: http://www.geeksforgeeks.org/archives/19267
| B*******1
发帖数: 2454 | 6 似乎可以吧，刚测试了一下，没有发现不对啊。
测了这几个例子
72 cout << "-----------------Test 1--------------------" << endl;
73 int test1[] = {1, -2, 4, -2, 6, 7};
74 getSubArray(test1, sizeof(test1)/sizeof(int), 7);
75
76 cout << "-----------------Test 2--------------------" << endl;
77 int test2[] = {1,1,1,1,-1};
78 getSubArray(test2, sizeof(test2)/sizeof(int), 3);
79
80
81 cout << "-----------------Test 3--------------------" << endl;
82 int test3[] = {1,1,1,1,0,-1,0,-1,1};
83 getSubArray(test3, sizeof(test3)/sizeof(int), 3);
84
85
86 cout << "-----------------Test 4--------------------" << endl;
87 int test4[] = {1,1,1,1,0,-1,0,1};
88 getSubArray(test4, sizeof(test4)/sizeof(int), 3);
输出为
-----------------Test 1--------------------
1 -2 4 -2 6
-----------------Test 2--------------------
1 1 1 -1
-----------------Test 3--------------------
1 1 1 0 -1 0 -1 1
-----------------Test 4--------------------
1 1 1 0 -1 0 1
楼主的例子也过了。 你的例子输出 1 1 1 -1
【在 h****e 的大作中提到】
: 那个O(N)解法看来不行，甚至不能扩展到求最长子数列和为定值的
: 题目，尤其是有零和负数的时候，例如给定数列{1,1,1,1,-1}
: 和定值3。
| s*********5
发帖数: 514 | 7 那个例子是求和相等，完全不是一回事了
这个题目只能DP, try all n*(n+1)/2 combination | B*******1
发帖数: 2454 | 8 我是说参考，我把code改了套在这个问题上的。 你可以给个反例我试验一下吗。
谢谢。
【在 s*********5 的大作中提到】
: 那个例子是求和相等，完全不是一回事了
: 这个题目只能DP, try all n*(n+1)/2 combination
| v****c
发帖数: 29 | 9 你的code怎么写的？
{1,1,100,-100,1}，定值是3的话怎么做？
【在 B*******1 的大作中提到】
: 我是说参考，我把code改了套在这个问题上的。 你可以给个反例我试验一下吗。
: 谢谢。
| B*******1
发帖数: 2454 | 10 多谢指点，这个case没有过看来的确不行。
【在 v****c 的大作中提到】
: 你的code怎么写的？
: {1,1,100,-100,1}，定值是3的话怎么做？
| | | v****c
发帖数: 29 | 11 大概想了个linear的算法
假设数组是A={1,-1,10,-7,9,-8}，要求和<=3
1. 计算partial sum：S={0,1,0,10,3,12,5}
方便起见，我在S最前面加了一个0
原问题转化为找离的最远的i
2. partial sum中从第一个数开始找递增序列L，这个例子：L=0->1->10->12
最长序列只能从这些数开始，我们不需要考虑其他的，比如S[1]=0
因为如果S[j]-S[1]<=3的话，S[j]-S[0]必定<=3
3. 让一个指针p指向L的最后一个元素，一个指针q指向S的最后一个元素
while(p)
{
while(*q > p->value + 3)
--q;
// 从p到q是一个valid的序列，记录长度
......
p=p->prev;
}
4. 最后得到最长的序列，这个例子中p指向S[0]，q指向S[4]，对应的序列是{1,-1,10,
-7}
【在 B*******1 的大作中提到】
: 多谢指点，这个case没有过看来的确不行。
| Z*****Z
发帖数: 723 | 12 谢谢回复，早晨去接人了，刚回来。
我发帖时的想法就就是keep一个current sum和两个指针，前面那个指针不停地走，更新
current sum，如果sum大于要找的target，就前进后面的指针，同时减少sum。这个对于
输入是正数和0的情况，并且寻找的解是<=target时应该是对的吧？
有了负数之后这个就不对了。
BT是穷举所有的可能，复杂度也不过O（N2）
然后还可以用二分，猜一个长度L，然后在O（N）的时间内verify。总复杂度NlogN，是
吧？
这就研究一下vimabc的算法。
【在 p*****2 的大作中提到】
: 你先说说你啥思路？
| Z*****Z
发帖数: 723 | 13 对的！这个和找最大的i < j 使得 A[i] < A[j]是一样的。
【在 v****c 的大作中提到】
: 大概想了个linear的算法
: 假设数组是A={1,-1,10,-7,9,-8}，要求和<=3
: 1. 计算partial sum：S={0,1,0,10,3,12,5}
: 方便起见，我在S最前面加了一个0
: 原问题转化为找离的最远的i: 2. partial sum中从第一个数开始找递增序列L，这个例子：L=0->1->10->12
: 最长序列只能从这些数开始，我们不需要考虑其他的，比如S[1]=0
: 因为如果S[j]-S[1]<=3的话，S[j]-S[0]必定<=3
: 3. 让一个指针p指向L的最后一个元素，一个指针q指向S的最后一个元素
: while(p)
| C***U
发帖数: 2406 | 14 赞第二步～！
【在 v****c 的大作中提到】
: 大概想了个linear的算法
: 假设数组是A={1,-1,10,-7,9,-8}，要求和<=3
: 1. 计算partial sum：S={0,1,0,10,3,12,5}
: 方便起见，我在S最前面加了一个0
: 原问题转化为找离的最远的i: 2. partial sum中从第一个数开始找递增序列L，这个例子：L=0->1->10->12
: 最长序列只能从这些数开始，我们不需要考虑其他的，比如S[1]=0
: 因为如果S[j]-S[1]<=3的话，S[j]-S[0]必定<=3
: 3. 让一个指针p指向L的最后一个元素，一个指针q指向S的最后一个元素
: while(p)
| C***U
发帖数: 2406 | | j****a
发帖数: 1277 | 16 n^2 DP
less
【在 Z*****Z 的大作中提到】
: 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, -2, 6, 7}
: maxsum=7
: the result would be: {1,-2, 4, -2, 6}
: 感觉用两个指针一前一后扫一遍数组就行了？求证。。。
: 出处：
: http://www.mitbbs.com/bbsann2/life.faq/JobHunting/17/D128425435
: 2821_2.C0/%C0%B4%B5%C0%C4%D1%D2%BB%B5%E3%B5%C4%CC%E2
| s********0
发帖数: 34 | 17 额 后来想了下 应该是递增 然后我就删了 呵呵
【在 C***U 的大作中提到】
: 这里应该是递增
: 那个i
| j********e
发帖数: 1192 | 18 首先，partial sum你计算错了，最后一个数是4，不是5.
最好的结果是{-1, 10, -7, 9, -8}.
算法本身好像没有问题。
大概想了个linear的算法
假设数组是A={1,-1,10,-7,9,-8}，要求和<=3
1. 计算partial sum：S={0,1,0,10,3,12,5}
方便起见，我在S最前面加了一个0
原问题转化为找离的最远的i
2. partial sum中从第一个数开始找递增序列L，这个例子：L=0->1->10->12
最长序列只能从这些数开始，我们不需要考虑其他的，比如S[1]=0
因为如果S[j]-S[1]<=3的话，S[j]-S[0]必定<=3
3. 让一个指针p指向L的最后一个元素，一个指针q指向S的最后一个元素
while(p)
{
while(*q > p->value + 3)
--q;
// 从p到q是一个valid的序列，记录长度
......
p=p->prev;
}
4. 最后得到最长的序列，这个例子中p指向S[0]，q指向S[4]，对应的序列是{1,-1,10,
-7}
【在 v****c 的大作中提到】
: 大概想了个linear的算法
: 假设数组是A={1,-1,10,-7,9,-8}，要求和<=3
: 1. 计算partial sum：S={0,1,0,10,3,12,5}
: 方便起见，我在S最前面加了一个0
: 原问题转化为找离的最远的i: 2. partial sum中从第一个数开始找递增序列L，这个例子：L=0->1->10->12
: 最长序列只能从这些数开始，我们不需要考虑其他的，比如S[1]=0
: 因为如果S[j]-S[1]<=3的话，S[j]-S[0]必定<=3
: 3. 让一个指针p指向L的最后一个元素，一个指针q指向S的最后一个元素
: while(p)
| b***e
发帖数: 1419 | 19 100, -100000, 1, 1, 1, ... (100000 1s)..., 100, 100, 100
target 400
【在 C***U 的大作中提到】
: 赞第二步～！
| v****c
发帖数: 29 | 20 这个例子好像没啥问题啊
partial sum是{0,100,-99900,...,100,200,300,400}
递增序列是0->100->200->300->400
【在 b***e 的大作中提到】
: 100, -100000, 1, 1, 1, ... (100000 1s)..., 100, 100, 100
: target 400
| | | b***e
发帖数: 1419 | 21 What is the result according to your algorithm?
【在 v****c 的大作中提到】
: 这个例子好像没啥问题啊
: partial sum是{0,100,-99900,...,100,200,300,400}
: 递增序列是0->100->200->300->400
| v****c
发帖数: 29 | 22 整个数组都是啊
一开始q指向最后一个，然后就不动了，p一直走到第一个
【在 b***e 的大作中提到】
: What is the result according to your algorithm?
| g**u
发帖数: 583 | 23
没弄明白,麻烦vimabc指点一下:
A={0,3,-2,2,2,1,-2}
target<=1
算出的 S={0,4,2,4,6,7,5}
算出L是 {0,4,6,7}
这样的得到的结果是什么呢?
期待的结果是:
{-2,2,2,1,-2}
【在 v****c 的大作中提到】
: 整个数组都是啊
: 一开始q指向最后一个，然后就不动了，p一直走到第一个
| i*********7
发帖数: 348 | 24 mark一下，最近没在啃算法，回头再看看大家讨论吧 | v****c
发帖数: 29 | 25 I think in your example A should be {0,4,-2,2,2,1,-2}.
S and L are correct for this A.
initially: p=7,q=5, it is valid because 5<=7+1
next: p=6,q=5, still valid
next: p=4,q=5, still valid
next: p=0, move q until q<=p+target, so in the end q=0
p=4,q=5, corresponding to {-2,2,2,1,-2}, is the best sequence found.
【在 g**u 的大作中提到】
:
: 没弄明白,麻烦vimabc指点一下:
: A={0,3,-2,2,2,1,-2}
: target<=1
: 算出的 S={0,4,2,4,6,7,5}
: 算出L是 {0,4,6,7}
: 这样的得到的结果是什么呢?
: 期待的结果是:
: {-2,2,2,1,-2}
| i*********7
发帖数: 348 | 26 int* findmaxsumarray(int *array, int length, int maxsum){
int *sum = new int[length + 1];
sum[0] = 0;
for(int i = 1; i <= length; i++)
sum[i] = sum[i - 1] + array[i - 1];
int *max = new int[length + 1];
int *min = new int[length + 1];
for(int i = 0;i<=length;i++)
cout<
cout<
max[0] = 0;
for(int i = 1; i < length + 1;i++)
{
max[i] = std::max(max[i - 1], sum[i]);
}
min[length] = sum[length];
for(int i = length - 1 ; i >= 0; i--){
min[i] = std::min(min[i + 1], sum[i]);
}
int prev = 0,next = 0;
int rightmost = 0,leftmost = 0;
while(prev != length + 1 && next != length + 1){
if(min[next] - max[prev] <= maxsum){
if(next != prev){
if(next - prev > rightmost - leftmost){
rightmost = next;
leftmost = prev;
}
}
next++;
}
else
prev++;
}
int *res = new int[rightmost - leftmost];
for(int i = leftmost; i < rightmost; i++){
cout<
res[i - leftmost] = array[i];
}
cout<
return res;
}
这是我关于这题的算法代码。
求测试，求轻拍 | p********s
发帖数: 37 | 27 呵呵我猜是对的。。
其实觉得也不用求和，楼上思路本质就是预处理把所有负数往左merge。因为如果a[i+1
]是负数的话选了a[i]肯定要再选a[i+1]，所以直接看成一个整体就行了。于是转化为
一串正数，求起来就直接了。 | a*******y
发帖数: 1040 | 28 这个longest increasing sequence当场都未必能写出来
【在 j********e 的大作中提到】
: 首先，partial sum你计算错了，最后一个数是4，不是5.
: 最好的结果是{-1, 10, -7, 9, -8}.
: 算法本身好像没有问题。
:
: 大概想了个linear的算法
: 假设数组是A={1,-1,10,-7,9,-8}，要求和<=3
: 1. 计算partial sum：S={0,1,0,10,3,12,5}
: 方便起见，我在S最前面加了一个0
: 原问题转化为找离的最远的i: 2. partial sum中从第一个数开始找递增序列L，这个例子：L=0->1->10->12
| s*******y
发帖数: 44 | 29 这个最长的序列不是{-1,10,-7,9,-8}吗？为什么是{1,-1,10,-7}？
另外为什么partial sum从第一个数开始找递增序列？S中可能有负数的，极端一点，A
全是负数，要求和小于一个负数，这个递增序列就找不到了。
大概想了个linear的算法
假设数组是A={1,-1,10,-7,9,-8}，要求和<=3
1. 计算partial sum：S={0,1,0,10,3,12,5}
方便起见，我在S最前面加了一个0
原问题转化为找离的最远的i
2. partial sum中从第一个数开始找递增序列L，这个例子：L=0->1->10->12
最长序列只能从这些数开始，我们不需要考虑其他的，比如S[1]=0
因为如果S[j]-S[1]<=3的话，S[j]-S[0]必定<=3
3. 让一个指针p指向L的最后一个元素，一个指针q指向S的最后一个元素
while(p)
{
while(*q > p->value + 3)
--q;
// 从p到q是一个valid的序列，记录长度
......
p=p->prev;
}
4. 最后得到最长的序列，这个例子中p指向S[0]，q指向S[4]，对应的序列是{1,-1,10,
-7}
【在 v****c 的大作中提到】
: 大概想了个linear的算法
: 假设数组是A={1,-1,10,-7,9,-8}，要求和<=3
: 1. 计算partial sum：S={0,1,0,10,3,12,5}
: 方便起见，我在S最前面加了一个0
: 原问题转化为找离的最远的i: 2. partial sum中从第一个数开始找递增序列L，这个例子：L=0->1->10->12
: 最长序列只能从这些数开始，我们不需要考虑其他的，比如S[1]=0
: 因为如果S[j]-S[1]<=3的话，S[j]-S[0]必定<=3
: 3. 让一个指针p指向L的最后一个元素，一个指针q指向S的最后一个元素
: while(p)
| w****g
发帖数: 727 | |
|
