字符串极值题解

题目链接

题目分析

现将字符串转化为数列，对于一个序列：

在枚举序列时，记 (i) 为当前数的下标。

可以记录 (now) 值为最大的 ([k,i]) 中序列和的值 ((1leq k leq i))，(ans) 为最终的答案。

令初始 (now=0)，每读入一个新数 (x)：

• 如果 (x>0)，(now+=x)，(ans=max(ans,now))；
• 如果 (x<0)，且 (now+x>0)，(now+=x)；
• 如果 (x<0)，且 (now+x leq 0)，直接令 (now=0)。

上面这个过程不能解决序列全是负数的情况，如果出现序列中全是负数的情况，特判即可：

因为序列中没有数值为 (0) 的数，所以在任意时刻，如果 (now=0)，则目前序列中的数都为负数。只需要根据这一特性特判即可。

参考代码

#include <iostream>
#include <cstdio>
#include <cstring>
#define ll long long
using namespace std;

int change(char ch) //将字母转换为对应的值
{
    int ans;
    if ('a' <= ch && ch <= 'z')
        ans = -(ch - 'a' + 1);
    else
        ans = (ch - 'A' + 1);
    return ans;
}

ll T, n, maxn, now, len;
string str;
int main()
{
    cin >> T;
    while (T--) //多组数据
    {
        cin >> str;
        len = str.size();   //求串的长度
        now = change(str[0]); //扫描第一个数，赋值给 now

        maxn = now; //此时更新答案
        if (now < 0)    //如果 now 为负数，直接舍弃前面
            now = 0;   

        for (int i = 1; i < len; ++i)   //字符串下标从0开始
        {
            ll x = change(str[i]);  //数

            if (x > 0)  //正数
            {
                now += x;
                maxn = max(now, maxn);
            }
            else    //负数
            {
                if (now + x < 0)    //加上 x 之后使得 now<0
                {
                    if (now == 0)   //特判全是负数的情况
                        maxn = max(x, maxn);
                    else   
                        now = 0;
                }
                else    //加上 x 之后 now>0
                    now += x;
                    // 因为 x 是负数，所以没必要更新ans
            }
        }
        printf("%lld
", maxn);
    }
    return 0;
}