I**A
发帖数: 2345 | 1 Given an array of integers. Imagine it as a pyramid as below:
a[]={1,2,3,4,5,6,7,8,9,10}
1
2 3
4 5 6
7 8 9 10
find a path from level 1 to last level such that the sum is maximum. The
path is such that its children should be reachable.
Ex:
1,2,5,9 is a path
1,2,6,10 is not a path since 6 is not reachable from 2.
The array is not sorted and numbers are random. | f*********5
发帖数: 576 | 2 结构肯定是
a[0]
a[1],a[2]
a[3],a[4],a[5],
....
right?
this is onsite or phone?
【在 I**A 的大作中提到】
: Given an array of integers. Imagine it as a pyramid as below:
: a[]={1,2,3,4,5,6,7,8,9,10}
: 1
: 2 3
: 4 5 6
: 7 8 9 10
: find a path from level 1 to last level such that the sum is maximum. The
: path is such that its children should be reachable.
: Ex:
: 1,2,5,9 is a path
| I**A
发帖数: 2345 | 3 careercup上看来的，貌似是phone interview。。
结构是对的，金字塔
第一个level有1个
第2个level有2个
...
第n个level有n个
...
【在 f*********5 的大作中提到】
: 结构肯定是
: a[0]
: a[1],a[2]
: a[3],a[4],a[5],
: ....
: right?
: this is onsite or phone?
| j**w
发帖数: 382 | 4 Use DP.
In each a[i], compute the accumulated sum AS[i] by
MAX(AS[j], AS[j+1], AS[j+2])+a[i], where a[j], a[j+1], and a[j+2] are one
level up for node a[i].
Say a[n] is
10
20 33
31 16 27
19 02 34 25
AS is
10
30 43
74 59 60
93 76 94 85
The final ans is 94, and the path can be found by the back pointers. | I**A
发帖数: 2345 | 5 首先赞一个，这个DP算法很合理。
两个问题
1） 你是说104，是么？
10－43－70－104
2） 你怎么理解这个reachable？
我觉得每个node可reach的downside只有两个,upside一个或者是两个，找一个node的
child比较简单，找parent就会稍微复杂一点点。。
比如 （不好意思， BBS会把下图的格式改掉，反正大致就是这么个金字塔的意思）
10
/ \
20 33
/ \ / \
31 16 27
/ \ / \ / \
19 02 34 25
我原来想的是for each node, get its two child, then use modified Dijkstra's
algorithm to find the maximum path to the leaf，
看了你的DP算法之后，得到提示， 可以用DP,从the second level from bottom 开始
go upward.. as[i] = max(as[i]ch
【在 j**w 的大作中提到】
: Use DP.
: In each a[i], compute the accumulated sum AS[i] by
: MAX(AS[j], AS[j+1], AS[j+2])+a[i], where a[j], a[j+1], and a[j+2] are one
: level up for node a[i].
: Say a[n] is
: 10
: 20 33
: 31 16 27
: 19 02 34 25
: AS is
| j**w
发帖数: 382 | 6
a[i+0] a[i+1] a[i+2] ...
a[j+0] a[j+1] a[j+2] a[j+3] ...
a node can be reached by the one just one level up, and up and left, if
any, and up and right, if any.
Say, a[j+1] can be reached by a[i+1], the left of a[i+1] (a[i+0] here),
and the right of a[i+1] (a[i+2] here).
That's my 2 cent
【在 I**A 的大作中提到】
: 首先赞一个，这个DP算法很合理。
: 两个问题
: 1） 你是说104，是么？
: 10－43－70－104
: 2） 你怎么理解这个reachable？
: 我觉得每个node可reach的downside只有两个,upside一个或者是两个，找一个node的
: child比较简单，找parent就会稍微复杂一点点。。
: 比如 （不好意思， BBS会把下图的格式改掉，反正大致就是这么个金字塔的意思）
: 10
: / \
| I**A
发帖数: 2345 | 7 hmm, we should ask the interviewer about how to define reachable..
based on your cents, then a[j+3] can only be reached by a[i+2} since it does
not have a up node, right?
could you please describe how you can get a node's reachable up nodes?
thanks..
given a index i, find its one or two or three reachable up node..
【在 j**w 的大作中提到】
:
: a[i+0] a[i+1] a[i+2] ...
: a[j+0] a[j+1] a[j+2] a[j+3] ...
: a node can be reached by the one just one level up, and up and left, if
: any, and up and right, if any.
: Say, a[j+1] can be reached by a[i+1], the left of a[i+1] (a[i+0] here),
: and the right of a[i+1] (a[i+2] here).
: That's my 2 cent
| l******4
发帖数: 729 | 8 这问题用uniform cost search就行了，解决任意reachable问题。
最优，并且complete | d****2
发帖数: 6250 | 9 跟DP没关系，DFS exhaustive search. | d****2
发帖数: 6250 | | | | s*****n
发帖数: 956 | 11 我被Amazon问到了一个类似的。
给定一个全是正数的数组，要求从中找出一些数使得sum最大，并且每个数都不相邻。
比如
3 2 5 9
结果就是 3 9
没做出来。 | I**A
发帖数: 2345 | 12 This one is basically same as the one I posted and based on the same thought
as my understanding of reachable...
Imagine the array are two trees, with the first and second element as roots,
respectively.. And then for each tree, find the path which gives the
largest sum by applying DP. Choose the larger one..
for instance, the array 3 2 5 9 6 7
the first ree is
3
5 9
6 7
The second tree is
2
9 6
7
。
【在 s*****n 的大作中提到】
: 我被Amazon问到了一个类似的。
: 给定一个全是正数的数组，要求从中找出一些数使得sum最大，并且每个数都不相邻。
: 比如
: 3 2 5 9
: 结果就是 3 9
: 没做出来。
| D***h
发帖数: 183 | 13 我觉得你想多了.
S[i] = max{S[i-1], a[i]+S[i-2]}, i=1,2....n
thought
roots,
【在 I**A 的大作中提到】
: This one is basically same as the one I posted and based on the same thought
: as my understanding of reachable...
: Imagine the array are two trees, with the first and second element as roots,
: respectively.. And then for each tree, find the path which gives the
: largest sum by applying DP. Choose the larger one..
: for instance, the array 3 2 5 9 6 7
: the first ree is
: 3
: 5 9
: 6 7
| I**A
发帖数: 2345 | 14 好像不对吧， 你看
a[n] 3 2 5 9
s[n] 3 2 8 11
it should be 3+9 instead.
【在 D***h 的大作中提到】
: 我觉得你想多了.
: S[i] = max{S[i-1], a[i]+S[i-2]}, i=1,2....n
:
: thought
: roots,
| a******e
发帖数: 710 | 15 应该是
S[i] = max{S[i-1], a[i]+S[i-2], a[i]+S[i-3]}, i=4,5....n
在这个最优的序列中，任意两个数在原来的数列中的间隔最多是2，所以要考虑S[i-3]
a[n] 3 2 5 9
s[n] 3 2 8 12
【在 D***h 的大作中提到】
: 我觉得你想多了.
: S[i] = max{S[i-1], a[i]+S[i-2]}, i=1,2....n
:
: thought
: roots,
| I**A
发帖数: 2345 | 16 嗯，这个应该是对的
多谢！这个的确是要简单些。。
你对我post的原题有何想法？
【在 a******e 的大作中提到】
: 应该是
: S[i] = max{S[i-1], a[i]+S[i-2], a[i]+S[i-3]}, i=4,5....n
: 在这个最优的序列中，任意两个数在原来的数列中的间隔最多是2，所以要考虑S[i-3]
: a[n] 3 2 5 9
: s[n] 3 2 8 12
| D***h
发帖数: 183 | 17 S[i] = max{S[i-1], a[i]+S[i-2]},就够了.
S[i]表示到a[i]以前的最大序列（可以包括a[i],也可以不包括a[i]）。
a[n] 3 2 5 9
s[n] 3 3 8 12
【在 a******e 的大作中提到】
: 应该是
: S[i] = max{S[i-1], a[i]+S[i-2], a[i]+S[i-3]}, i=4,5....n
: 在这个最优的序列中，任意两个数在原来的数列中的间隔最多是2，所以要考虑S[i-3]
: a[n] 3 2 5 9
: s[n] 3 2 8 12
| I**A
发帖数: 2345 | 18 也对，就是初始化的时候注意一下就成了。。
s[1]= max(a[0],a[1])
然后循环从2开始
【在 D***h 的大作中提到】
: S[i] = max{S[i-1], a[i]+S[i-2]},就够了.
: S[i]表示到a[i]以前的最大序列（可以包括a[i],也可以不包括a[i]）。
: a[n] 3 2 5 9
: s[n] 3 3 8 12
|
|
