请问丝瓜雌蕾才1.5公分就黄掉了是缺什么肥料么 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>gardening - 拈花惹草

请问丝瓜雌蕾才1.5公分就黄掉了是缺什么肥料么

请问丝瓜雌蕾才1.5公分就黄掉了是缺什么肥料么# gardening - 拈花惹草

k*e2012-08-13 07:08

1 楼

input: a circular array
output: a subvector of the array that has max sum
可以想象排列在圆周上的n个元素，求连续的k个使得其和最大
我的想法是
1. take any element as the leader and break the circle into one dimensional
array a[1:n]. use the classical method to get the maxsum subvector
2. we did not consider the case that the maxsum subvector in the circle
passes a[1]. in the next step we will figure out the maxsum subvector that
passes a[1], suppose it is a[n - i:j].
3. claim: a[j+1:n-i-1] is the minsum subvector of a[1:n]. beca

d*t2012-08-13 07:08

2 楼

丝瓜好多雌蕾才1.5公分左右都黄掉了。请问是缺什么肥料么，是不是水浇多了？现在
补救还来得及么？
谢谢。

w*p2012-08-13 07:08

3 楼

额觉得，这道题的关键不是array is circle or not. 因为我们只能用array来表达
circle array. circle array 只是多了几步边界问题。
搂主提到的“classical method to get the maxsum subvector“，不知道running
time 是多少。
我的方法是土土的将相临的K个数加起来。包括circle的情况。时间是 O(K*N)，空间
是O（N)
不知道，有没有人更好的方法
dynamic 在这道题中应该用不着吧。

g*e2012-08-13 07:08

4 楼

丝瓜是瓜类里最耐涝的，水多的可能性比较小。加些磷肥试试。

g*y2012-08-13 07:08

5 楼

1.K是一个任意的数
2.不管K是固定的，还是任意的，都只要O(N)

【在 w********p 的大作中提到】

: 额觉得，这道题的关键不是array is circle or not. 因为我们只能用array来表达
: circle array. circle array 只是多了几步边界问题。
: 搂主提到的“classical method to get the maxsum subvector“，不知道running
: time 是多少。
: 我的方法是土土的将相临的K个数加起来。包括circle的情况。时间是 O(K*N)，空间
: 是O（N)
: 不知道，有没有人更好的方法
: dynamic 在这道题中应该用不着吧。

n*72012-08-13 07:08

6 楼

没受粉

w*p2012-08-13 07:08

7 楼

根据你提供的algorithm and feedback, 从写思路. one time scan
running time O(n) space O(1)
Please correct me, if logic error
//n is the array size
maxSum=-99999999;
if (k>n) return failed
for (int i=0; istartIndex=i;
endIndex= (i+k-1)% n;
//get the sum of k number from startIndex to endIndex
sum=SumKMember(startIndex, endIndex， sum);
if (sum>maxSum ) { maxSum = sum; retrunIndex=startIndex }
}
//get sum only one time scan
int SumKMember(int startIndex, int endIndex, sum) {

【在 k***e 的大作中提到】

: input: a circular array
: output: a subvector of the array that has max sum
: 可以想象排列在圆周上的n个元素，求连续的k个使得其和最大
: 我的想法是
: 1. take any element as the leader and break the circle into one dimensional
: array a[1:n]. use the classical method to get the maxsum subvector
: 2. we did not consider the case that the maxsum subvector in the circle
: passes a[1]. in the next step we will figure out the maxsum subvector that
: passes a[1], suppose it is a[n - i:j].
: 3. claim: a[j+1:n-i-1] is the minsum subvector of a[1:n]. beca

d*t2012-08-13 07:08

8 楼

还没开花呢，怎么授粉啊。

H*M2012-08-13 07:08

9 楼

呼吁geniusxsy出手
刚实现了下,发现远比我想象的要难.
在classical 非circular array的那个问题上改的
但是复杂了许多.还出错....
please test: 1 2 4 -3 5 2
should return 14, not 11.

【在 g*******y 的大作中提到】

: 1.K是一个任意的数
: 2.不管K是固定的，还是任意的，都只要O(N)

d*t2012-08-13 07:08

10 楼

请问磷肥用fish fertilizer好还是bone meal好？有什么可推荐的么？
谢谢。

【在 g***e 的大作中提到】

: 丝瓜是瓜类里最耐涝的，水多的可能性比较小。加些磷肥试试。

l*r2012-08-13 07:08

11 楼

duplicate the array

【在 H*M 的大作中提到】

: 呼吁geniusxsy出手
: 刚实现了下,发现远比我想象的要难.
: 在classical 非circular array的那个问题上改的
: 但是复杂了许多.还出错....
: please test: 1 2 4 -3 5 2
: should return 14, not 11.

m*i2012-08-13 07:08

12 楼

丝瓜死掉2/3正常。

H*M2012-08-13 07:08

13 楼

没用的
我的思想就是duplicate the array
你implement看看就知道了

【在 l*******r 的大作中提到】

: duplicate the array

g*e2012-08-13 07:08

14 楼

我用过bone meal和super phosphate。

【在 d*****t 的大作中提到】

: 请问磷肥用fish fertilizer好还是bone meal好？有什么可推荐的么？
: 谢谢。

w*p2012-08-13 07:08

15 楼

code is here, I run it simply, it looks good
O(n) for running time, and O(1) for space
#include
#include
#include
using namespace std;
int SumKMember(int iArray[],int startIndex, int endIndex, int sum);
int main (int argc, char *args[]) {
if (argc != 2) {
cout<return 0;
}
int k=atoi(args[1]);
//n is the array size
int maxSum=-99999999;

int iArray[] = {1, 2 , 4 , -3, 5 ,2};
int n = sizeof( iArray) /sizeof

d*t2012-08-13 07:08

16 楼

多谢高手指点。

g*y2012-08-13 07:08

17 楼

这题的题意应该是，找一段长度任意的子数组使得和最大，k不是一个给定的参数。

【在 w********p 的大作中提到】

: code is here, I run it simply, it looks good
: O(n) for running time, and O(1) for space
: #include
: #include
: #include
: using namespace std;
: int SumKMember(int iArray[],int startIndex, int endIndex, int sum);
: int main (int argc, char *args[]) {
: if (argc != 2) {
: cout<

l*i2012-08-13 07:08

18 楼

enn...Your solution is correct.

dimensional
[j

【在 k***e 的大作中提到】

l*i2012-08-13 07:08

19 楼

dynamic programming...in linear time

【在 w********p 的大作中提到】

w*p2012-08-13 07:08

20 楼

这要是我的面试题，就这样fail了。：（

【在 g*******y 的大作中提到】

: 这题的题意应该是，找一段长度任意的子数组使得和最大，k不是一个给定的参数。

H*M2012-08-13 07:08

21 楼

有O(1) space的
我说的是非circular

【在 l***i 的大作中提到】

:
: dynamic programming...in linear time

g*y2012-08-13 07:08

22 楼

呵呵，不是你的错，怪krone转述的题目误导你了，呵呵

【在 w********p 的大作中提到】

: 这要是我的面试题，就这样fail了。：（

H*M2012-08-13 07:08

23 楼

不过可以考虑设定k, 另外一道面试题
呵呵

【在 g*******y 的大作中提到】

: 呵呵，不是你的错，怪krone转述的题目误导你了，呵呵

m*f2012-08-13 07:08

24 楼

那数组里应该还有负数，要不然和最大得数组当然是长度=n...
这个题总体来说题意不太清楚, 一般如果面试题要考虑负数的话，肯定会说明

【在 g*******y 的大作中提到】

: 这题的题意应该是，找一段长度任意的子数组使得和最大，k不是一个给定的参数。

m*f2012-08-13 07:08

25 楼

设定k求最大连续和? 那不是太容易了吗?

【在 H*M 的大作中提到】

: 不过可以考虑设定k, 另外一道面试题
: 呵呵

l*i2012-08-13 07:08

26 楼

...the standard dynamic programming can be implemented with O(1) extra space
...
The equation is
f(i) = max(a_i, f(i-1)+a_i)...
Hence at any time you need only f(i-1)...

【在 H*M 的大作中提到】

: 有O(1) space的
: 我说的是非circular

H*M2012-08-13 07:08

27 楼

ok,we are talking about the same thing
usually when we talk about DP, i am thinking of extra space
space

H*M2012-08-13 07:08

28 楼

请5分钟内写对 :)

【在 m*****f 的大作中提到】

: 设定k求最大连续和? 那不是太容易了吗?

H*M2012-08-13 07:08

29 楼

原楼主的方法好像是对的
现算一个maxconsum,再算minconsum（对非circular）,再用sum-minconsum,比谁大
没想到有什么不妥的地方。好像也能用同样的方法算minconsum..

【在 l***i 的大作中提到】

: enn...Your solution is correct.
:
: dimensional
: [j

w*p2012-08-13 07:08

30 楼

俺嘬觉得O(1)space 还是可以的
1。先说说普通non-circle array. 可以用非dynamic programing O(n)runing time,
O(1) space 。关键是sum<0时，就drop, goto next
2. circle array, 向楼上说的在负数那段开，记住当前maxSum开始的 index,
计算到end of array 时继续，一直到one element before 当前maxSum开始的 index
ex1: -3, 5, 2, 1, 4, => 一只计算到5, 2, 1, 4, -3 got solution 5, 2, 1 , 4
ex2: −2, 1, −3, 4, −1, 2, 1, −2, 4 => 当前maxSum开始
4, −1, 2, 1, −2, 4, -2, 1, -3 got solution 4, -1, 2, 1, -2, 4

H*M2012-08-13 07:08

31 楼

我觉得楼主本来的idea就很好
至少我还没看出破绽

,
4

【在 w********p 的大作中提到】

: 俺嘬觉得O(1)space 还是可以的
: 1。先说说普通non-circle array. 可以用非dynamic programing O(n)runing time,
: O(1) space 。关键是sum<0时，就drop, goto next
: 2. circle array, 向楼上说的在负数那段开，记住当前maxSum开始的 index,
: 计算到end of array 时继续，一直到one element before 当前maxSum开始的 index
: ex1: -3, 5, 2, 1, 4, => 一只计算到5, 2, 1, 4, -3 got solution 5, 2, 1 , 4
: ex2: −2, 1, −3, 4, −1, 2, 1, −2, 4 => 当前maxSum开始
: 4, −1, 2, 1, −2, 4, -2, 1, -3 got solution 4, -1, 2, 1, -2, 4

w*p2012-08-13 07:08

32 楼

高度同意
我只是在丢脸后，试图找点回来

【在 H*M 的大作中提到】

: 我觉得楼主本来的idea就很好
: 至少我还没看出破绽
:
: ,
: 4

H*M2012-08-13 07:08

33 楼

mm不要自责
前进让梦更近
-Toyota

【在 w********p 的大作中提到】

: 高度同意
: 我只是在丢脸后，试图找点回来

k*e2012-08-13 07:08

34 楼

晕我贴了很长时间没人理
有mm（或貌似mm id）的回帖就立马一堆人回
看来弄个马甲很有必要
ps，我以为人人都知道给定 one dim array，找连续的sub array使得和最大
：）因为在programming pearl和许多算法课的作业里出现过
结果。。。
再次推荐没有读过变成珍珠读下这本书

【在 w********p 的大作中提到】

: 高度同意
: 我只是在丢脸后，试图找点回来

s*x2012-08-13 07:08

35 楼

no, it is f(i) = max(a_i, f(i-1)+a_i, f(i-1))
and sure it is linear time algorithm no matter whether the array is circular
or not. the circular case can be treated as array. not so precisely
speaking:
a b c d - circular case is ALMOST equivalent to solve a b c d a b c d - non-
circular, since any factor of the circular word is a factor of that normal
word.

space

【在 l***i 的大作中提到】

: ...the standard dynamic programming can be implemented with O(1) extra space
: ...
: The equation is
: f(i) = max(a_i, f(i-1)+a_i)...
: Hence at any time you need only f(i-1)...

l*i2012-08-13 07:08

36 楼

Obviously you shouldn't do that...
You may connect disconnected pieces by adding f(i-1) there...
It's true that you need an O(n) scan to return max f(i) as the final answer.
..

【在 s*x 的大作中提到】

: no, it is f(i) = max(a_i, f(i-1)+a_i, f(i-1))
: and sure it is linear time algorithm no matter whether the array is circular
: or not. the circular case can be treated as array. not so precisely
: speaking:
: a b c d - circular case is ALMOST equivalent to solve a b c d a b c d - non-
: circular, since any factor of the circular word is a factor of that normal
: word.
:
: space

l*i2012-08-13 07:08

37 楼

enn... minsum(a1,...,an) = -maxsum(-a1,...,-an)...
This is just theoretical analysis (re-using an existing argument always
keeps proofs simple) -- One needn't implement it in this way though...

【在 H*M 的大作中提到】

: 原楼主的方法好像是对的
: 现算一个maxconsum,再算minconsum（对非circular）,再用sum-minconsum,比谁大
: 没想到有什么不妥的地方。好像也能用同样的方法算minconsum..