logo
Redian新闻
>未名空间
>Parenting - 为人父母
>
哪里买12 quart plastic container?
avatar
哪里买12 quart plastic container?# Parenting - 为人父母
Z*Z
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
avatar
o*a
2 楼
Preschool 要家长准备12 quart 的container, 11"x6"x13" , 我在target 和amazon
上没有看到完全符合标准的...请问在哪里可以买到？谢谢
avatar
p*2
3 楼
你先说说你啥思路？
avatar
h*r
4 楼
差不多大就行了
可以去staples， lowes 看看

【在 o*********a 的大作中提到】
: Preschool 要家长准备12 quart 的container, 11"x6"x13" , 我在target 和amazon
: 上没有看到完全符合标准的...请问在哪里可以买到？谢谢
avatar
h*e
5 楼
你觉得可以给出线性的解法？数字可正可负的话，我觉得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
avatar
h*e
7 楼
那个O(N)解法看来不行，甚至不能扩展到求最长子数列和为定值的
题目，尤其是有零和负数的时候，例如给定数列{1,1,1,1,-1}
和定值3。

【在 B*******1 的大作中提到】
: 是不是可以用这里的方法？
: http://www.geeksforgeeks.org/archives/19267
avatar
B*1
8 楼
似乎可以吧，刚测试了一下，没有发现不对啊。
测了这几个例子
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。
avatar
s*5
9 楼
那个例子是求和相等，完全不是一回事了
这个题目只能DP, try all n*(n+1)/2 combination
avatar
B*1
10 楼
我是说参考，我把code改了套在这个问题上的。 你可以给个反例我试验一下吗。
谢谢。

【在 s*********5 的大作中提到】
: 那个例子是求和相等，完全不是一回事了
: 这个题目只能DP, try all n*(n+1)/2 combination
avatar
v*c
11 楼
你的code怎么写的？
{1,1,100,-100,1}，定值是3的话怎么做？

【在 B*******1 的大作中提到】
: 我是说参考，我把code改了套在这个问题上的。 你可以给个反例我试验一下吗。
: 谢谢。
avatar
B*1
12 楼
多谢指点，这个case没有过看来的确不行。

【在 v****c 的大作中提到】
: 你的code怎么写的？
: {1,1,100,-100,1}，定值是3的话怎么做？
avatar
v*c
13 楼
大概想了个linear的算法
假设数组是A={1,-1,10,-7,9,-8}，要求和<=3
1. 计算partial sum：S={0,1,0,10,3,12,5}
方便起见，我在S最前面加了一个0
原问题转化为找离的最远的i2. 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没有过看来的确不行。
avatar
Z*Z
14 楼
谢谢回复，早晨去接人了，刚回来。
我发帖时的想法就就是keep一个current sum和两个指针，前面那个指针不停地走，更新
current sum，如果sum大于要找的target，就前进后面的指针，同时减少sum。这个对于
输入是正数和0的情况，并且寻找的解是<=target时应该是对的吧？
有了负数之后这个就不对了。
BT是穷举所有的可能，复杂度也不过O（N2）
然后还可以用二分，猜一个长度L，然后在O（N）的时间内verify。总复杂度NlogN，是
吧？
这就研究一下vimabc的算法。

【在 p*****2 的大作中提到】
: 你先说说你啥思路？
avatar
Z*Z
15 楼
对的！这个和找最大的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)
avatar
C*U
16 楼
赞第二步～！

【在 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)
avatar
C*U
17 楼
这里应该是递增
那个i
avatar
j*a
18 楼
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
avatar
s*0
19 楼
额 后来想了下 应该是递增 然后我就删了 呵呵

【在 C***U 的大作中提到】
: 这里应该是递增
: 那个i
avatar
j*e
20 楼
首先，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
原问题转化为找离的最远的i2. 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)
avatar
b*e
21 楼
100, -100000, 1, 1, 1, ... (100000 1s)..., 100, 100, 100
target 400

【在 C***U 的大作中提到】
: 赞第二步～！
avatar
v*c
22 楼
这个例子好像没啥问题啊
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
avatar
b*e
23 楼
What is the result according to your algorithm?

【在 v****c 的大作中提到】
: 这个例子好像没啥问题啊
: partial sum是{0,100,-99900,...,100,200,300,400}
: 递增序列是0->100->200->300->400
avatar
v*c
24 楼
整个数组都是啊
一开始q指向最后一个，然后就不动了，p一直走到第一个

【在 b***e 的大作中提到】
: What is the result according to your algorithm?
avatar
g*u
25 楼

没弄明白,麻烦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一直走到第一个
avatar
i*7
26 楼
mark一下，最近没在啃算法，回头再看看大家讨论吧
avatar
v*c
27 楼
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}
avatar
i*7
28 楼
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;
}
这是我关于这题的算法代码。
求测试，求轻拍
avatar
p*s
29 楼
呵呵我猜是对的。。
其实觉得也不用求和，楼上思路本质就是预处理把所有负数往左merge。因为如果a[i+1
]是负数的话选了a[i]肯定要再选a[i+1]，所以直接看成一个整体就行了。于是转化为
一串正数，求起来就直接了。
avatar
a*y
30 楼
这个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
avatar
s*y
31 楼
这个最长的序列不是{-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
原问题转化为找离的最远的i2. 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)
avatar
w*g
32 楼
排序之后再做是nlogn吧
相关阅读
发个说明 （为确保都能看见，星期一晚上删除）咨询一下：没上kindergarten,可不可以上一年级[bssd]吃喝拉撒，没有不操心的。问撒的问题国人重理工，老美爱文科[合集] 论坛发帖应该论事不论人鼓励多发实战贴打压大棒回帖请问视力表倒数第三行是多少？挑战名校对亚裔的种族歧视 －－Blum 5月30日到湾区亲自解析哈佛和德州大学诉讼请教关于娃以后上学的啥基金什么的如何消除孩子的恐惧感（转载）提个醒，要买火腿和羊腿的同学注意了 (转载)《Nature》最新关于青少年近视原因的文章带5岁娃回国一星期男娃，取这三个名，哪个最好， 谢谢从藤校讨论到吃叉子天才与早育ABC男为什么这么多单身的？ (转载)这些不当的家教方式，你有吗？（转载）娃给了我一个惊喜，也有一个问题请问电子画板？TV Ads that Hurt ALL Asian Americans?
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。