题目

题目链接

题目分析

低配版的最大子段和问题

首先需要注意题目中的两个要点：最长和连续。同时，题目对于“偶串”的定义为：由很多长度为的、两字符相同的字符串拼接而成的字符串。这意味着，每当发现一个长度为的两字符相同的子串（比如aa, bb, cc），我们就可以将这个子串暂时去掉后，与该字符串最后一个字符相连的最长偶串长度

发现了吗？其实这种算法就是Kadane算法，只是这里是个低配版的。下面给出递推式：

规定：下标从开始，

AC code

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

const int N = 2e5;
int kadane[N+10];

int main()
{
    string str; cin >> str;
    str = '0' + str;  // 调整下标方便对齐
    int res = 0;
    kadane[1] = 0, kadane[0] = 0;
    for( size_t i = 2; i < str.size(); i ++ ){
        if( str[i] == str[i-1] )
            kadane[i] = kadane[i-2] + 2;
        res = max(res, kadane[i]);
    }
    cout << res;
    return 0;
}

WA解法

这里提供一个WA解法供大家避雷：贪心算法

遇到一个字符（从第二个字符开始），我们考虑两种情况：

1. 如果该字符前面一个与自身相同，那么tmp += 2，指针向后挪个单元
2. 否则，res = max(res, tmp)，tmp清零，指针向后挪个单元

核心代码如下：

int tmp = 0, res = 0;
for( size_t i = 2; i < str.size(); i ++ ){  // str[0]填充无关字符
	if( str[i] == str[i-1] ) tmp += 2, i ++;  // 结束后一定会挪一个单元，这里先挪一个单元，1+1=2
  	else{
    	res = max(res, tmp);
      	tmp = 0;
    }
}
res = max(res, tmp);

给出两组Hack数据：