求这道题的O(N)解 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>Programming - 葵花宝典

求这道题的O(N)解

求这道题的O(N)解# Programming - 葵花宝典

a*t2017-12-11 08:12

1 楼

一般contract都是一年一签，虽说是一年的position,但其实只是9个月的，第一年8月
到第二年的5月。这种情况，暑假到底算不算employed？
尤其是,如果第二年8月份开始新工作，5-8月算不算是unemployed的gap状态,引起身份
问题？

a*a2017-12-11 08:12

2 楼

在北京春晚演出了。估计是那英运作的
唱歌哞哞的

s*a2017-12-11 08:12

3 楼

同胞血汗撒foxconn
百万爱派过大洋
换个壳子今胜昔
加点feature抢而光
必将存款送苹果
不去孝敬爹与娘
惠普黑妹俱往矣
抢钱正道是奸商

h*j2017-12-11 08:12

4 楼

A: array of N integer, N (1, 100K), A[i] (-10M, 10M)
for two index P,Q
0<=P<=Qfind the maximum(A[P]+A[Q]+Q-P) among all PQ pairs

n*l2017-12-11 08:12

5 楼

算是Gap,前几天本版讨论过解决办法。

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

: 一般contract都是一年一签，虽说是一年的position,但其实只是9个月的，第一年8月
: 到第二年的5月。这种情况，暑假到底算不算employed？
: 尤其是,如果第二年8月份开始新工作，5-8月算不算是unemployed的gap状态,引起身份
: 问题？

t*b2017-12-11 08:12

6 楼

应该不是，北京春晚找了一堆好声音的人：
http://v.aibuka.com/watch/11277

w*22017-12-11 08:12

7 楼

这个对苹果恨之入骨呀。。lol

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

: 同胞血汗撒foxconn
: 百万爱派过大洋
: 换个壳子今胜昔
: 加点feature抢而光
: 必将存款送苹果
: 不去孝敬爹与娘
: 惠普黑妹俱往矣
: 抢钱正道是奸商

p*o2017-12-11 08:12

8 楼

你这是少了个绝对值把？

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

a*t2017-12-11 08:12

9 楼

有人提到，如果把9个月工资平均到12月，就没有gap了？

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

: 算是Gap,前几天本版讨论过解决办法。

c*h2017-12-11 08:12

10 楼

根本不合格律，哈哈。

★ 发自iPhone App: ChineseWeb - 中文网站浏览器

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

: 同胞血汗撒foxconn
: 百万爱派过大洋
: 换个壳子今胜昔
: 加点feature抢而光
: 必将存款送苹果
: 不去孝敬爹与娘
: 惠普黑妹俱往矣
: 抢钱正道是奸商

h*j2017-12-11 08:12

11 楼

真没有绝对值

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

: 你这是少了个绝对值把？

s*l2017-12-11 08:12

12 楼

自身的经验，毫无问题。

s*a2017-12-11 08:12

13 楼

我师法主席豪放派，你们女人不懂的。

【在 c*****h 的大作中提到】

: 根本不合格律，哈哈。
:
: ★ 发自iPhone App: ChineseWeb - 中文网站浏览器

w*g2017-12-11 08:12

14 楼

老夫给你们解一下吧。
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*12017-12-11 08:12

15 楼

我们学校都是把工资分到十二个月发，没GAP

c*h2017-12-11 08:12

16 楼

赞主席豪放派。

★ 发自iPhone App: ChineseWeb - 中文网站浏览器

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

: 我师法主席豪放派，你们女人不懂的。

w*m2017-12-11 08:12

17 楼

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没有耦合，所以内部循环省了。

r*y2017-12-11 08:12

18 楼

黄牛对万里，也不是对仗啊

【在 c*****h 的大作中提到】

: 根本不合格律，哈哈。
:
: ★ 发自iPhone App: ChineseWeb - 中文网站浏览器

w*g2017-12-11 08:12

19 楼

线下开着呢。奔个照片吧
http://www.aaalgo.com/hidden/
现有美女帅哥各一枚，那位老板缺人帮我招了去吧。
手慢无，上次来问的那个美女已经进fb啦。
我是organic training，人不多。

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

: wdong开个python刷题班吧

c*h2017-12-11 08:12

20 楼

不很工整，但也算对仗啊。
否则古人很多律也不对仗了。

★ 发自iPhone App: ChineseWeb - 中文网站浏览器

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

: 黄牛对万里，也不是对仗啊

d*a2017-12-11 08:12

21 楼

帅哥啊，我怎么觉得见过。

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

: 线下开着呢。奔个照片吧
: http://www.aaalgo.com/hidden/
: 现有美女帅哥各一枚，那位老板缺人帮我招了去吧。
: 手慢无，上次来问的那个美女已经进fb啦。
: 我是organic training，人不多。

p*92017-12-11 08:12

22 楼

我觉得这几句写的特别好，catty指点一下，哈哈哈
白日如厕须“祖母”，
“三丧”作伴好还乡。
即穿马甲去苹果，
便下黑帖当小强。

【在 c*****h 的大作中提到】

: 不很工整，但也算对仗啊。
: 否则古人很多律也不对仗了。
:
: ★ 发自iPhone App: ChineseWeb - 中文网站浏览器

w*r2017-12-11 08:12

23 楼

现在国内老总都长那样儿， lol

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

: 帅哥啊，我怎么觉得见过。

r*y2017-12-11 08:12

24 楼

货无只恨黄牛恶，路远唯呼万里迢。
意思也不流畅。路远，万里迢，纯属没意义的复文。
不如：
货乏只恨黄牛恶，路远何堪黑市嚣。

【在 c*****h 的大作中提到】

: 不很工整，但也算对仗啊。
: 否则古人很多律也不对仗了。
:
: ★ 发自iPhone App: ChineseWeb - 中文网站浏览器

d*a2017-12-11 08:12

25 楼

卫东，我觉得这个算法应该这样来写：
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 的大作中提到】

s*a2017-12-11 08:12

26 楼

跟主席的字一样豪放哦 ^0^

【在 c*****h 的大作中提到】

: 赞主席豪放派。
:
: ★ 发自iPhone App: ChineseWeb - 中文网站浏览器

x*o2017-12-11 08:12

27 楼

这个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

T*n2017-12-11 08:12

28 楼

这个炼句不错

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

: 货无只恨黄牛恶，路远唯呼万里迢。
: 意思也不流畅。路远，万里迢，纯属没意义的复文。
: 不如：
: 货乏只恨黄牛恶，路远何堪黑市嚣。

l*m2017-12-11 08:12

29 楼

美女真不错

：线下开着呢。奔个照片吧
：

s*a2017-12-11 08:12

30 楼

改了，请继续不吝赐教

【在 c*****h 的大作中提到】

: 根本不合格律，哈哈。
:
: ★ 发自iPhone App: ChineseWeb - 中文网站浏览器

c*h2017-12-11 08:12

31 楼

嗯，原来那句意思赘述我也不太满意。你这个黑市改得还不错，就是跟路远意思不太搭
干。
我原本前句想写因黄牛之故天朝ipad无货，后句接着说但是去美国路太远果粉想只能望
洋兴叹。

★ 发自iPhone App: ChineseWeb - 中文网站浏览器

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

: 货无只恨黄牛恶，路远唯呼万里迢。
: 意思也不流畅。路远，万里迢，纯属没意义的复文。
: 不如：
: 货乏只恨黄牛恶，路远何堪黑市嚣。

c*h2017-12-11 08:12

32 楼

你这是从新韵还是古韵?
貌似无论哪个都出律了。你这当属首句平起平收式，找格律自己对对吧。

★ 发自iPhone App: ChineseWeb - 中文网站浏览器

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

: 改了，请继续不吝赐教

s*a2017-12-11 08:12

33 楼

同胞血汗撒福康，
百万挨拍过大洋。
添俩“功能”新胜旧，
换张屏幕抢而光。
钱多人傻奸商笑，
质次价高忠粉伤。
惠普黑莓俱往矣，
谷歌微软赶超忙。
注：福康 = foxconn，挨拍 = ipad
因为前面有批评说不合格律，故特此修订，这下和律了吧 ^0^。一个平仄都没错哦。

w*22017-12-11 08:12

34 楼

这个对苹果恨之入骨呀。。lol

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

: 同胞血汗撒foxconn
: 百万爱派过大洋
: 换个壳子今胜昔
: 加点feature抢而光
: 必将存款送苹果
: 不去孝敬爹与娘
: 惠普黑妹俱往矣
: 抢钱正道是奸商

c*h2017-12-11 08:12

35 楼

根本不合格律，哈哈。

★ 发自iPhone App: ChineseWeb - 中文网站浏览器

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

: 同胞血汗撒foxconn
: 百万爱派过大洋
: 换个壳子今胜昔
: 加点feature抢而光
: 必将存款送苹果
: 不去孝敬爹与娘
: 惠普黑妹俱往矣
: 抢钱正道是奸商

s*a2017-12-11 08:12

36 楼

我师法主席豪放派，你们女人不懂的。

【在 c*****h 的大作中提到】

: 根本不合格律，哈哈。
:
: ★ 发自iPhone App: ChineseWeb - 中文网站浏览器

c*h2017-12-11 08:12

37 楼

赞主席豪放派。

★ 发自iPhone App: ChineseWeb - 中文网站浏览器

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

: 我师法主席豪放派，你们女人不懂的。

r*y2017-12-11 08:12

38 楼

黄牛对万里，也不是对仗啊

【在 c*****h 的大作中提到】

: 根本不合格律，哈哈。
:
: ★ 发自iPhone App: ChineseWeb - 中文网站浏览器

c*h2017-12-11 08:12

39 楼

不很工整，但也算对仗啊。
否则古人很多律也不对仗了。

★ 发自iPhone App: ChineseWeb - 中文网站浏览器

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

: 黄牛对万里，也不是对仗啊

p*92017-12-11 08:12

40 楼

: 不很工整，但也算对仗啊。
: 否则古人很多律也不对仗了。
:
: ★ 发自iPhone App: ChineseWeb - 中文网站浏览器

r*y2017-12-11 08:12

41 楼

: 不很工整，但也算对仗啊。
: 否则古人很多律也不对仗了。
:
: ★ 发自iPhone App: ChineseWeb - 中文网站浏览器

s*a2017-12-11 08:12

42 楼

跟主席的字一样豪放哦 ^0^

【在 c*****h 的大作中提到】

: 赞主席豪放派。
:
: ★ 发自iPhone App: ChineseWeb - 中文网站浏览器

T*n2017-12-11 08:12

43 楼

这个炼句不错

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

: 货无只恨黄牛恶，路远唯呼万里迢。
: 意思也不流畅。路远，万里迢，纯属没意义的复文。
: 不如：
: 货乏只恨黄牛恶，路远何堪黑市嚣。

s*a2017-12-11 08:12

44 楼

改了，请继续不吝赐教

【在 c*****h 的大作中提到】

: 根本不合格律，哈哈。
:
: ★ 发自iPhone App: ChineseWeb - 中文网站浏览器

c*h2017-12-11 08:12

45 楼

: 货无只恨黄牛恶，路远唯呼万里迢。
: 意思也不流畅。路远，万里迢，纯属没意义的复文。
: 不如：
: 货乏只恨黄牛恶，路远何堪黑市嚣。

c*h2017-12-11 08:12

46 楼

: 改了，请继续不吝赐教

s*a2017-12-11 08:12

47 楼

包子还没收到！！

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

: 同胞血汗撒福康，
: 百万挨拍过大洋。
: 添俩“功能”新胜旧，
: 换张屏幕抢而光。
: 钱多人傻奸商笑，
: 质次价高忠粉伤。
: 惠普黑莓俱往矣，
: 谷歌微软赶超忙。
: 注：福康 = foxconn，挨拍 = ipad
: 因为前面有批评说不合格律，故特此修订，这下和律了吧 ^0^。一个平仄都没错哦。