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

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

求这道题的O(N)解 (转载)

求这道题的O(N)解 (转载)# JobHunting - 待字闺中

h*j2017-12-11 08:12

1 楼

【以下文字转载自 Programming 讨论区】
发信人: hpj (江湖), 信区: Programming
标题: 求这道题的O(N)解
发信站: BBS 未名空间站 (Sun Dec 10 23:54:45 2017, 美东)
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

g*g2017-12-11 08:12

2 楼

So easy.
Two arrays:
C: max{1..i} A[j] + j
D: max{i..N} A[j] - j
max {C_i+D_i}

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

: 【以下文字转载自 Programming 讨论区】
: 发信人: hpj (江湖), 信区: Programming
: 标题: 求这道题的O(N)解
: 发信站: BBS 未名空间站 (Sun Dec 10 23:54:45 2017, 美东)
: 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

d*l2017-12-11 08:12

3 楼

Max(A[i]+i+max(A[j]-j)) for j<=I

z*t2017-12-11 08:12

4 楼

记录两个变量
v1 ：max(A[x] - x) for any x visited
v2 : max(A[x] + A[y] + y - x) for any x,y visited where y > x
for循环更新v1和v2。
for (int i = 0; i < A.size(); i++)
{
v2 = max(v2, v1 + A[i] + i);
v1 = max(v1, A[i] - i);
}
return v2;