c++ - 字符串中的 Rs 数

Question

我有一个作业，我得到一个包含字母“R”和“K”的字符串 S，例如“RRRRKKKKRK”。

我需要通过将字符 i 到 j 翻转到它们的相反位置来获得该字符串可能包含的 'R' 的最大数量。所以:

for(int x = i; x < j; x++)
{
  if S[x] = 'R'
  {
    S[X] = 'S';
  }
  else
  {
    S[X] = 'R';
  }
}

但是，我只能进行上述调用一次。

所以对于上面的例子:“RRRRKKKKRK”。

您将有 i = 4 和 j = 8，这将导致:“RRRRRRRRKR”，然后您将在结果字符串中输出 R 的数量:9。

我的代码部分有效，但在某些情况下无效。谁能找出缺少的内容？

示例输入

2
RKKRK
RKKR

示例输出

4
4

我的解决方案

我的解决方案只适用于第一种情况，我不知道我缺少什么来完成算法:

int max_R = INT_MIN;
for (int i = 0; i < s.size(); i++)
{
    for (int j = i + 1; j < s.size(); j++)
    {
        int cnt = 0;
        string t = s;

        if (t[j] == 'R')
        {
            t[j] = 'K';
        }
        else
        {
            t[j] = 'R';
        }

        for (int b = 0; b < s.size(); b++)
        {
            if (t[b] == 'R')
            {
                cnt++;

                if (cnt  > max_R)
                {
                    max_R = cnt;
                }
            }

        }
    }

}


cout << max_R << endl;

Answer 1

把它变成 Maximum subarray problem 怎么样？哪个有O(n)解？

遍历字符串一次，给“K”赋值 1，给“R”赋值 -1。

例如，对于 'RKRRKKKKRKK'，您生成一个数组 -> [-1, 1, -1, -1, 1, 1, 1, 1, -1, 1, 1 ] -> [-1, 1, -2, 4, -1, 2](为了更清楚，我将连续的 -1 和 1 分组)

在生成的数组上应用 Kadane 的算法。你这样做得到的是你可以通过翻转 'K' 获得的 'R' 的最大数量。

继续这个例子，你会发现最大子数组是[4, -1, 2]，和为5。

现在将此子数组外的负值的绝对值与您的最大子数组之和相加以获得答案。

在我们的例子中，只有 -1 和 -2 是负数并且在子数组之外。我们得到 |-1| + |-2| + 5 = 8