Redian新闻
>
请问丝瓜雌蕾才1.5公分就黄掉了是缺什么肥料么
avatar
请问丝瓜雌蕾才1.5公分就黄掉了是缺什么肥料么# gardening - 拈花惹草
k*e
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
avatar
d*t
2
丝瓜好多雌蕾才1.5公分左右都黄掉了。请问是缺什么肥料么,是不是水浇多了?现在
补救还来得及么?
谢谢。
avatar
w*p
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 在这道题中应该用不着吧。
avatar
g*e
4
丝瓜是瓜类里最耐涝的,水多的可能性比较小。加些磷肥试试。
avatar
g*y
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 在这道题中应该用不着吧。

avatar
n*7
6
没受粉
avatar
w*p
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

avatar
d*t
8
还没开花呢,怎么授粉啊。
avatar
H*M
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)

avatar
d*t
10
请问磷肥用fish fertilizer好还是bone meal好?有什么可推荐的么?
谢谢。

【在 g***e 的大作中提到】
: 丝瓜是瓜类里最耐涝的,水多的可能性比较小。加些磷肥试试。
avatar
l*r
11
duplicate the array

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

avatar
m*i
12
丝瓜死掉2/3正常。
avatar
H*M
13
没用的
我的思想就是duplicate the array
你implement看看就知道了

【在 l*******r 的大作中提到】
: duplicate the array
avatar
g*e
14
我用过bone meal和super phosphate。

【在 d*****t 的大作中提到】
: 请问磷肥用fish fertilizer好还是bone meal好?有什么可推荐的么?
: 谢谢。

avatar
w*p
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
avatar
d*t
16
多谢高手指点。
avatar
g*y
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<
avatar
l*i
18
enn...Your solution is correct.

dimensional
[j

【在 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

avatar
l*i
19

dynamic programming...in linear time

【在 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<
avatar
w*p
20
这要是我的面试题, 就这样fail了。 :(

【在 g*******y 的大作中提到】
: 这题的题意应该是,找一段长度任意的子数组使得和最大,k不是一个给定的参数。
avatar
H*M
21
有O(1) space的
我说的是非circular

【在 l***i 的大作中提到】
:
: dynamic programming...in linear time

avatar
g*y
22
呵呵,不是你的错,怪krone转述的题目误导你了,呵呵

【在 w********p 的大作中提到】
: 这要是我的面试题, 就这样fail了。 :(
avatar
H*M
23
不过可以考虑设定k, 另外一道面试题
呵呵

【在 g*******y 的大作中提到】
: 呵呵,不是你的错,怪krone转述的题目误导你了,呵呵
avatar
m*f
24
那数组里应该还有负数, 要不然和最大得数组当然是长度=n...
这个题总体来说题意不太清楚, 一般如果面试题要考虑负数的话, 肯定会说明

【在 g*******y 的大作中提到】
: 这题的题意应该是,找一段长度任意的子数组使得和最大,k不是一个给定的参数。
avatar
m*f
25
设定k求最大连续和? 那不是太容易了吗?

【在 H*M 的大作中提到】
: 不过可以考虑设定k, 另外一道面试题
: 呵呵

avatar
l*i
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

avatar
H*M
27
ok,we are talking about the same thing
usually when we talk about DP, i am thinking of extra space
space
avatar
H*M
28
请5分钟内写对 :)

【在 m*****f 的大作中提到】
: 设定k求最大连续和? 那不是太容易了吗?
avatar
H*M
29
原楼主的方法好像是对的
现算一个maxconsum,再算minconsum(对非circular),再用sum-minconsum,比谁大
没想到有什么不妥的地方。 好像也能用同样的方法算minconsum..

【在 l***i 的大作中提到】
: enn...Your solution is correct.
:
: dimensional
: [j

avatar
w*p
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
avatar
H*M
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

avatar
w*p
32
高度同意
我只是在丢脸后,试图找点回来

【在 H*M 的大作中提到】
: 我觉得楼主本来的idea就很好
: 至少我还没看出破绽
:
: ,
: 4

avatar
H*M
33
mm不要自责
前进让梦更近
-Toyota

【在 w********p 的大作中提到】
: 高度同意
: 我只是在丢脸后,试图找点回来

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

【在 w********p 的大作中提到】
: 高度同意
: 我只是在丢脸后,试图找点回来

avatar
s*x
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)...

avatar
l*i
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

avatar
l*i
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..

相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。