文章

119

粉丝

68

获赞

92

访问

20.2k

头像
字符串区间翻转 题解:Kadana算法(卡丹算法)
P1642 杭州电子科技大学机试题
发布于2025年2月7日 16:57
阅读数 94

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int maxOnesAfterFlip(int n, const string& s) {
    int original_ones = 0; // 原始字符串中 1 的数量
    for (char c : s) {
        if (c == '1') original_ones++;
    }

    int max_gain = 0;      // 最大增益
    int current_gain = 0;  // 当前增益

    for (int i = 0; i < n; ++i) {
        // 计算当前字符的贡献
        int value = (s[i] == '0') ? 1 : -1;

        // 更新当前增益
        current_gain += value;

        // 如果当前增益为负,重置当前增益
        if (current_gain < 0) {
            current_gain = 0;
        }

        // 更新最大增益
        max_gain = max(max_gain, current_gain);
    }

    // 如果没有增益,返回原始 1 的数量
    if (max_gain <= 0) {
        return original_ones;
    }

    // 返回翻转后的最大 1 的数量
    return original_ones + max_gain;
}

int main() {
    int n;
    while(cin>>n){
        string s;
        cin>>s;
        int ans=maxOnesAfterFlip(n,s);
      ...
登录查看完整内容


登录后发布评论

暂无评论,来抢沙发