简答题 偏难
#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

4
-1 2 3 0

输出样例 1

5

输入样例 2

5
-3 4 -5 1 3

输出样例 2

5

数据范围

对于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 &lt;= qr and q[ql] &lt; i - n: ql += 1 ans = max(ans, pre[i] - pre[q[ql]]) while ql &lt;= qr and pre[i] &lt; pre[q[qr]]: qr -= 1 qr += 1 q[qr] = i print(ans)</pre>
这道题暂未补解析。