526互联

【每日一题】Problem 327A - Flipping Game

发布时间 2023-06-09 23:24:00作者: HelloEricy

原题

解决思路

计算数字 "1" 的最大数目，可以转换成计算数组最大和，即求 \(maxSum(oldArraySum - (1 \rightarrow 0) + (0 \rightarrow 1)) \Rightarrow oldArraySum + maxSum(flipSum)\)

误区

注意: 题目要求必须执行一次，因此起始值不是 0 而是 -1

#include <bits/stdc++.h>

int main() {
    int n; std::cin >> n;
    std::vector<int> vec(n, 0);
    for (int i = 0; i < n; ++i) std::cin >> vec[i];

    int sum, flipSum, oldSum;
    sum = flipSum = -1, oldSum = 0;
    for (int i = 0; i < n; ++i) {
        oldSum += vec[i];

        if (flipSum < 0) flipSum = 0;
        flipSum += 1 - 2 * vec[i];
        sum = std::max(sum, flipSum);
    }

    std::cout << oldSum + sum << std::endl;

    return 0;
}