3

一个仅包含 0 和 1 的数组作为输入给出。您可以选择数组 i 和 j 的任意两个索引并翻转它们之间的所有元素（即 0->1 和 1->0）。求翻转后得到的数组的最大和。例如：对于 [0,1,0,0,1,0]，答案是 4。（从索引 2 翻转到 3）。

这是我的方法：
1）为数组中的所有索引找到前缀总和（保持在 sum[i] 中）。
2）翻转原始数组中的所有位。
3) 使用 Kadane 的算法找到最大子数组和 MAXSUM。令最大子数组的开始和结束索引为 i 和 j。
4) 答案是 sum(i-1)+MAXSUM+sum(n-1)-sum(j)。

请告诉我我的方法是否正确。

4

1 回答 1

2

实际上，您可以在一次遍历数组时非常轻松地做到这一点。您跟踪当前翻转位的范围有多好。只要您处于积极状态，当前范围就可以优先于任何后续范围。但是一旦你达到零或负数，你应该放弃你的范围并开始一个新的范围。

例如，如果您发现翻转索引 0..5 会导致 +4，那么这很好，并且您希望将 0..5 作为您的范围的一部分，因为只有在您也要翻转时它才会使您受益指数 6..X。但是如果 0..5 结果为 -1，您不想使用 0..5，因为这只会降低您的分数。因此，那时您将从 6..6 重新开始。也许在代码中更容易看到。这是一个一次性解决问题的 C 版本：

// Returns best range (start..end) to flip, and best score achieved.
static void findRange(const int *array, int *pStart, int *pEnd, int *pScore)
{
    int start     = 0;
    int best      = 0;
    int i         = 0;
    int diff      = 0;
    int base      = 0;
    int bestStart = -1;
    int bestEnd   = -1;

    // Count the number of 1s in the array already.
    for (i=0;i<N;i++)
        base += array[i];

    // Run through the array, keeping track of "diff", which is how much
    // we have gained by flipping the bits from "start" to "i".
    for (i=start=0;i<N;i++) {
        // Flip the number at i.
        if (array[i] == 0)
            diff++;
        else
            diff--;
        // If this range (from start to i) is the best so far, remember it.
        if (diff > best) {
            bestStart = start;
            bestEnd   = i;
            best      = diff;
        }
        // If we get to a zero or negative difference, start over with a
        // new range starting from i+1.
        if (diff <= 0) {
            start = i+1;
            diff  = 0;
        }
    }
    *pStart = bestStart;
    *pEnd   = bestEnd;
    *pScore = base + best;
}

编辑：在阅读了 Kadane 的算法之后，事实证明我写的内容等同于使用 Kadane 来找到修改后的数组上的最大子数组，在该数组中将每个 0 切换为 1，将每个 1 切换为 -1。

于 2014-12-02T07:21:54.273 回答