获得最多的奖金

题目难度：二星
考察点：双指针

方法1：暴力、前缀和

1. 分析：
   我们按照题意进行计算，枚举第一刀下标i和第二刀的下标j即可，然后判断区间[1, i]和区间[j,n]的和是不是相等，如果相等记录答案，取最大值即可。在计算区间和的时候要注意的是需要提前预处理一下前缀和，要不然直接计算区间和的话会使得时间复杂度变高。

算法实现：
(1). 首先用一个数组sum计算前缀和。
(2). 枚举切两刀的两个下标i和j，计算区间[1,i]和[j,n]的值，那么区间[1,i]的和显然等于sum[i]，区间[j,n]的和则等于sum[n]-sum[j-1]，我们只需要判断这两个是否相等即可，相等则记录答案。
(3). 输出奖金最大值。

2. 复杂度分析：
   时间复杂度：O(n^2)
   空间复杂度：O(n)

3. 代码：

   #include <bits/stdc++.h>
   using namespace std;
   typedef long long LL;
   const int MAXN = 2e5+5;
   LL a[MAXN],sum[MAXN];
   int main() {
    int n; cin>>n;
    for(int i=1; i<=n; i++) {
        cin>>a[i];
        sum[i] = sum[i-1] + a[i];
    }
    LL ans = 0;
    for(int i=1; i<n; i++) {
        int tmp = sum[i];
        for(int j=i+1; j<=n; j++) {
            if(sum[n]-sum[j-1] == tmp) {
                ans = tmp;
            }
        }
    }
    cout<<ans<<endl;
    return 0;
   }

方法：双指针

1. 分析：
   这道题由于枚举耗费时间较多，所以我们采用双指针的方法，我们分别用左右指针l,r表示左右数组的和，即左指针l表示的是区间[1,r]的和，右指针r表示的是区间[r,n]的和，然后左右指针进行移动，移动规则如下：
   如果左数组的和大于右数组的和，右指针移动，同时记录右数组和，即sumr+=a[r--]。
   如果左数组的和小于右数组的和，左指针移动，同时记录左数组和，即suml+=a[l++]。
   如果左数组的和等于右数组的和，左右指针移动，同时记录答案和左右数组的和，即sumr+=a[r--], suml+=a[l++]。
   直至满足条件l > r，退出循环。

算法实现：
(1). 初始化左右指针l=1,r=n，同时初始化左右数组和suml=sumr=0。
(2). 按照之前的指针移动规则，即：
如果suml == sumr ，那么ans = suml, suml += a[l++], sumr += a[r--];
如果suml > sumr ，那么sumr += a[r--];
如果suml < sumr ，那么suml += a[l++];
(3). 输出奖金最大值ans。

2. 复杂度分析：
   时间复杂度：O(n)
   空间复杂度：O(n)

3. 代码：

   #include <bits/stdc++.h>
   using namespace std;
   typedef long long LL;
   const int MAXN = 2e5+5;
   LL a[MAXN];
   int main() {
    int n; cin>>n;
    for(int i=1; i<=n; i++) cin>>a[i];
    int l = 1, r = n;
    LL suml = a[l], sumr = a[r];
    LL ans = 0;
    while(l < r) {
        if(suml == sumr) {
            ans = suml;
            suml += a[++l];
            sumr += a[--r];
        }
        else if(suml > sumr) sumr += a[--r];
        else suml += a[++l];
    }
    cout<<ans<<endl;
    return 0;
   }