Maximizing 1s with a Single Flip: An Elegant Application of Kadane's Algorithm

Have you ever encountered an algorithmic problem that seems to require a brute-force approach, only to realize it can be transformed into a classic computer science pattern? The "Maximum Ones after at most 1 flip" problem is a perfect example of this.

Instead of checking every possible subarray to flip (which would take a sluggish O(N^2) time), we can reframe the problem and solve it in a blistering O(N) time using Kadane’s Algorithm.

Here is a breakdown of the problem, the core intuition, and a highly optimized Java solution.

---

The Problem

You are given an array consisting only of 0s and 1s. You are allowed to perform at most one flip operation. A flip operation consists of choosing a contiguous subarray and changing all 0s to 1s and all 1s to 0s.

Your goal is to return the maximum number of 1s you can achieve in the array after this operation.

---

The "Aha!" Moment: Reframing the Problem

At first glance, it feels like we need to simulate flips. But let's look at what a flip actually does to our total count of 1s:

• When we flip a 0, we gain a 1. (Net change: +1)
• When we flip a 1, we lose a 1. (Net change: -1)

This means we don't need to count the final 1s directly. We just need to find the contiguous subarray that gives us the maximum net gain. Finding the contiguous subarray with the maximum sum is the exact problem Kadane's Algorithm was built to solve!

The formula for our final answer becomes beautifully simple:
Total 1s = (Initial count of 1s) + (Maximum net gain from a flip)

---

The Step-by-Step Approach

1. Count the Baseline: First, we iterate through the array to count how many 1s we start with.
2. Early Exits (Optimizations): If the array is entirely 0s, flipping the whole array gives us length 1s. If the array is entirely 1s, or only has a single 0, doing zero flips (or flipping that one 0) already maxes out our possible 1s. We can return length immediately and save processing time.
3. Apply Kadane's: We iterate through the array again. We treat every 0 as a 1 (potential gain) and every 1 as a -1 (potential loss). We use Kadane's algorithm to keep a running sum and track the maximum peak.

---

The Java Solution

Here is the highly optimized O(N) solution utilizing O(1) space:

class Solution {
    int maxOnes(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }

        int length = arr.length;
        int oneCount = 0;

        // Step 1: Count initial 1s - O(N)
        for (int num : arr) {
            oneCount += num == 1 ? 1 : 0;
        }

        // Step 2: Handle edge cases where max possible 1s is already guaranteed
        // - No 1s (flip everything)
        // - All 1s (0 operations needed)
        // - Only one 0 (flip the single 0)
        if (oneCount == 0 || oneCount == length || oneCount == length - 1) {
            return length;
        }

        // Step 3: Find the maximum net gain using Kadane's Algorithm - O(N)
        int maximumSum = getMaximumSum(arr);

        // Calculate the final total
        int totalCount = oneCount + maximumSum;
        return totalCount < 0 ? 0 : totalCount;
    }

    private int getMaximumSum(int[] arr) {
        int runningSum = 0;
        int maximumSum = Integer.MIN_VALUE;

        for (int num : arr) {
            // Transform: 0 becomes +1 (gain), 1 becomes -1 (loss)
            runningSum += num == 1 ? -1 : 1;
            maximumSum = Math.max(maximumSum, runningSum);

            // If our running sum drops below zero, it's a net loss. 
            // We reset it to 0, effectively starting a new subarray.
            if (runningSum < 0) {
                runningSum = 0;
            }
        }

        return maximumSum;
    }
}

Complexity Analysis

Time Complexity: O(N)
We iterate through the array exactly twice—once to count the initial 1s, and once to calculate the maximum sum. O(2N) simplifies to O(N).

Space Complexity: O(1)
We only use a few primitive integer variables (oneCount, runningSum, maximumSum) to keep track of our state, regardless of how large the input array is.