简答题
偏难
#17749
环线 题目描述 小 A 喜欢坐地铁。地铁环线有 n个车站,依次以 1,2,...,n标号。车站 i( 1≤i<n)的下一个车站是车站i+1 。 特殊地,车站n…
环线
题目描述
小 A 喜欢坐地铁。地铁环线有 n个车站,依次以 1,2,...,n标号。车站 i( 1≤i<n)的下一个车站是车站i+1 。
特殊地,车站n 的下一个车站是车站1 。
小 A 会从某个车站出发,乘坐地铁环线到某个车站结束行程,这意味着小 A 至少会经过一个车站。小 A 不会经过一个车站多次。当小 A 乘坐地铁环线经过车站 i时,小 A 会获得 ai点快乐值。请你安排小 A 的行程,选择出发车站与结束车站,使得获得的快乐值总和最大。
输入格式
第一行,一个正整数n ,表示车站的数量。
第二行, n个整数a1,a2,...an, ,分别表示经过每个车站时获得的快乐值。
输出格式
一行,一个整数,表示小 A 能获得的最大快乐值。
输入样例 1
输出样例 1
输入样例 2
输出样例 2
数据范围
对于20% 的测试点,保证1≤n≤200 。
对于40 % 的测试点,保证 1≤n≤2000。
对于所有测试点,保证 1≤n≤2*105,-109≤ai≤109 。
答案与解析
正确答案:<pre class="brush:python;toolbar:false">n = int(input())
a = [0] + list(map(int, input().split()))
pre = [0 for i in range(2 * n + 5)]
for i in range(1, n + 1):
a.append(a[i])
for i in range(1, 2 * n + 1):
pre[i] = pre[i - 1] + a[i]
ql, qr, ans = 1, 1, -1e18
q = [0 for i in range(2 * n + 5)]
for i in range(1, 2 * n + 1):
while ql <= qr and q[ql] < i - n:
ql += 1
ans = max(ans, pre[i] - pre[q[ql]])
while ql <= qr and pre[i] < pre[q[qr]]:
qr -= 1
qr += 1
q[qr] = i
print(ans)</pre>
这道题暂未补解析。