题干：

在蒜厂年会上有一个抽奖，在一个环形的桌子上，有 nn 个纸团，每个纸团上写一个数字，表示你可以获得多少蒜币。但是这个游戏比较坑，里面竟然有负数，表示你要支付多少蒜币。因为这些数字都是可见的，所以大家都是不会出现的赔的情况。

游戏规则：每人只能抓一次，只能抓取一段连续的纸团，所有纸团上的数字和就是你可以获得的蒜币。

蒜头君作为蒜厂的一员在想，我怎么可以获得最多的蒜币呢？最多能获取多少蒜币呢？

因为年会是发奖，那么一定有大于 00 的纸团。

输入格式

第一行输入一个整数 nn，表示有 nn 个纸团。

第二行输入输入 nn 个整数 a_iai​，表示每个纸团上面写的数字（这些纸团的输入顺序就是环形桌上纸团的摆放顺序）。

输出格式

输出一个整数，表示蒜头君最多能获取多少蒜币。

数据范围

对于 30\%30% 的数据：1 \le n \le 10^2,-10^3 \le a_i \le 10^31≤n≤102,−103≤ai​≤103。

对于 60\%60% 的数据：1 \le n \le 5 \times 10^3,-10^6 \le a_i \le 10^61≤n≤5×103,−106≤ai​≤106。

对于 100\%100% 的数据：1 \le n \le 10^5,-10^9 \le a_i \le 10^91≤n≤105,−109≤ai​≤109。

样例输入复制

3
1 -2 1

样例输出复制

2

解题报告：

  单调队列优化dp。

AC代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int INF = 0x3f3f3f3f;
const LL mod = 1e9 + 7;
const int N = 200005;
int a[N];
LL pre[N];
int main() {
   int n;
   scanf("%d", &n);
   for (int i = 1; i <= n; i++) {
       scanf("%d", &a[i]);
       a[n + i] = a[i];
   }
   for (int i = 1; i <= 2 * n; i++) {
       pre[i] = pre[i - 1] + a[i];
   }
   deque<int> q;
   q.push_back(0);
   LL ans = a[1];
   for (int i = 1; i <= 2 * n; i++) {
       if (!q.empty() && q.front() < i - n) {
           q.pop_front();
       }
       ans = max(ans, pre[i] - pre[q.front()]);
       while (!q.empty() && pre[q.back()] >= pre[i]) {
           q.pop_back();
       }
       q.push_back(i);
   }
   printf("%lld\n", ans);
   return 0;
}

WA代码：（只通过60%）

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define ll long long
#define pb push_back
#define pm make_pair
#define fi first
#define se second
using namespace std;
const int MAX = 2e5 + 5;
ll a[MAX],dp[MAX],dpp[MAX];
int main()
{
	int n;
	cin>>n;
	for(int i = 1; i<=n; i++) cin>>a[i];
	ll sum = 0 ;
	for(int i = 1; i<=n; i++) {
		if(sum >=0) sum += a[i],dp[i] = sum;
		else sum = a[i],dp[i] = sum;
	}
	for(int i = 1; i<=n; i++) {
		if(sum >=0) sum += a[i],dpp[i] = sum;
		else sum = a[i],dpp[i] = sum;
	}
	cout << max(*max_element(dp+1,dp+n+1),*max_element(dpp+1,dpp+n+1));
	return 0 ;
 }

最暴力的做法：（肯定会T的）

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int INF = 0x3f3f3f3f;
const LL mod = 1e9 + 7;
const int N = 200005;
int a[N];
LL pre[N];
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        a[n + i] = a[i];
    }
    LL ans = a[1];
    for (int i = 1; i <= n; i++) {
        LL sum = 0;
        for (int j = i; j < i + n; j++) {
            sum += a[j];
            if (sum > ans) {
                ans = sum;
            }
        }
    }
    printf("%lld\n", ans);
    return 0;
}

另一个做法：

https://blog.csdn.net/weixin_41544329/article/details/85076111