摇摇晃摇

题目大意

给定一个只包含-1与1的序列，要求你执行一次操作使$a_i$与$a_{i+1}$变为相反的数字，相反的定义为1变-1,-1变1。从而使得该序列的总和最大。

思路解析

在序列当中，我们只能选择两个相邻的数字进行操作，那么只有可能有以下三种情况。

1. -1,-1 : 一旦遇到这种组合直接执行操作即可。
2. -1,1 或 1,-1 :在没有第一种情况下，如果我们想要数值最大，选定这两种情况翻转即可保持总数不变。
3. 1,1 : 当一和二的情况没有出现时，那么该序列只有可能全为1，我们才可以选择该情况进行操作。

我们可以先将数值总和$sum$计算出来，根据是否存在情况1、2、3决定将$sum + 4$ 或 $sum$不变 或$sum - 4$即可。

时间复杂度

$O(n)$

代码演示

/*
    Yuilice今天睡饱了吗？
*/
#include<bits/stdc++.h>
using namespace std;
int a[100005];

int main()
{
    int t;
    cin >> t;
    while(t--)
        {
            int n;
            cin >> n;
            int sum = 0 ;
            int last,x;
            cin >> last;
            sum += last;
            n -- ;
            bool flag = true;
            bool neq = false;
            while(n -- )
            {
               cin >> x;
                sum += x;
               if(last == -1 && x == -1 && flag)
                {
                  sum += 4;
                  flag = false;
                }
                if(last != x)
                {
                    neq = true;
                }
                last = x;
            }
            if(flag && !neq) sum -= 4;
            cout << sum << endl;
        }
    return 0;
}