h*j
发帖数: 393 | 1 A: array of N integer, N (1, 100K), A[i] (-10M, 10M)
for two index P,Q
0<=P<=Q
find the maximum(A[P]+A[Q]+Q-P) among all PQ pairs | p***o
发帖数: 1252 | 2 你这是少了个绝对值把？
【在 h*j 的大作中提到】
: A: array of N integer, N (1, 100K), A[i] (-10M, 10M)
: for two index P,Q
: 0<=P<=Q: find the maximum(A[P]+A[Q]+Q-P) among all PQ pairs
| h*j
发帖数: 393 | 3 真没有绝对值
【在 p***o 的大作中提到】
: 你这是少了个绝对值把？
| w***g
发帖数: 5958 | 4 老夫给你们解一下吧。
Q确定的话，
maximum(A[P]+A[Q]+Q-P) = maximum(A[P]-P)|P<=Q + A[Q]+Q
所以就是维护两个最大值：
foo = 至今看到过的最大的A[P]-P, 初始值负无穷大
bar = 至今看到过的最大的A[P]-P + A[Q]+Q， 初始指负无穷大
for i in range(N):
foo = max(foo, A[i] - i)
bar = max(bar, foo + A[i] + i)
走的是动归套路，但是A[P]-P和A[Q]+Q没有耦合，所以内部循环省了。
【在 h*j 的大作中提到】
: A: array of N integer, N (1, 100K), A[i] (-10M, 10M)
: for two index P,Q
: 0<=P<=Q: find the maximum(A[P]+A[Q]+Q-P) among all PQ pairs
| w********m
发帖数: 1137 | 5 wdong开个python刷题班吧
【在 w***g 的大作中提到】
: 老夫给你们解一下吧。
: Q确定的话，
: maximum(A[P]+A[Q]+Q-P) = maximum(A[P]-P)|P<=Q + A[Q]+Q
: 所以就是维护两个最大值：
: foo = 至今看到过的最大的A[P]-P, 初始值负无穷大
: bar = 至今看到过的最大的A[P]-P + A[Q]+Q， 初始指负无穷大
: for i in range(N):
: foo = max(foo, A[i] - i)
: bar = max(bar, foo + A[i] + i)
: 走的是动归套路，但是A[P]-P和A[Q]+Q没有耦合，所以内部循环省了。
| w***g
发帖数: 5958 | 6 线下开着呢。 奔个照片吧
http://www.aaalgo.com/hidden/
现有美女帅哥各一枚，那位老板缺人帮我招了去吧。
手慢无，上次来问的那个美女已经进fb啦。
我是organic training，人不多。
【在 w********m 的大作中提到】
: wdong开个python刷题班吧
| d***a
发帖数: 13752 | 7 帅哥啊，我怎么觉得见过。
【在 w***g 的大作中提到】
: 线下开着呢。 奔个照片吧
: http://www.aaalgo.com/hidden/
: 现有美女帅哥各一枚，那位老板缺人帮我招了去吧。
: 手慢无，上次来问的那个美女已经进fb啦。
: 我是organic training，人不多。
| w*****r
发帖数: 197 | 8 现在国内老总都长那样儿， lol
【在 d***a 的大作中提到】
: 帅哥啊，我怎么觉得见过。
| d***a
发帖数: 13752 | 9 卫东，我觉得这个算法应该这样来写：
AP_max_unlimited = -infinite
AP_max_limited = -infinite
AQ_max = -infinite
for i in range(N):
AP_max_unlimited = max(AP_max_unlimited, A[i]-i)
if (AQ_max + AP_max_limited < A[i] + i + AP_max_unlimited)
AQ_max = A[i] + i
AP_max_limited = AP_max_unlimited
else
AQ_max = max(AQ_max, A[i]+ i)
如果我写错了，那就是献丑了。:)
【在 w***g 的大作中提到】
: 老夫给你们解一下吧。
: Q确定的话，
: maximum(A[P]+A[Q]+Q-P) = maximum(A[P]-P)|P<=Q + A[Q]+Q
: 所以就是维护两个最大值：
: foo = 至今看到过的最大的A[P]-P, 初始值负无穷大
: bar = 至今看到过的最大的A[P]-P + A[Q]+Q， 初始指负无穷大
: for i in range(N):
: foo = max(foo, A[i] - i)
: bar = max(bar, foo + A[i] + i)
: 走的是动归套路，但是A[P]-P和A[Q]+Q没有耦合，所以内部循环省了。
| x********o
发帖数: 25 | 10 这个leetcode那个买卖股票的题有区别吗
【在 h*j 的大作中提到】
: A: array of N integer, N (1, 100K), A[i] (-10M, 10M)
: for two index P,Q
: 0<=P<=Q: find the maximum(A[P]+A[Q]+Q-P) among all PQ pairs
| l*******m
发帖数: 1096 | |
|
