h*j
发帖数: 393 | 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<=Q
find the maximum(A[P]+A[Q]+Q-P) among all PQ pairs | g*******g
发帖数: 50 | 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***l
发帖数: 7 | 3 Max(A[i]+i+max(A[j]-j)) for j<=I | z******t
发帖数: 25 | 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; |
|
