Fundamentals of Greedy Strategies

Greedy algorithms do not follow a rigid template. They essence lies in building a global optimum through a sequence of locally optimal choices. While formal proof of correctness is not mandatory for competitive programming (as long as the solution is accepted), a systematic approach helps:

1. Break the problem into smaller subproblems.
2. Determine an appropriate greedy criterion.
3. Solve each subproblem optimally.
4. Combine the local optimums into the final global result.

Satisfying the Largest Number of Children (Cookie Assignment)

Our goal is to maximize the number of content children given arrays of greed factors g and cookie sizes s.

The greedy insight: pairing the largest available cookie with largest unsatisfied greed leads to an optimal count. Both arrays are sorted first. Starting with the biggest cookie and the hungriest child, if the current cookie satisfies the child, we count it and move to the next smaller cookie. If not, that child cannot be satisfied by any remaining cookie, so we skip the child but keep the same cookie for the next greedy child.

int findContentChildren(vector<int>& greed, vector<int>& cookies) {
    sort(greed.begin(), greed.end());
    sort(cookies.begin(), cookies.end());
    int happy = 0;
    int ckIdx = cookies.size() - 1;
    for (int gIdx = greed.size() - 1; gIdx >= 0; --gIdx) {
        if (ckIdx >= 0 && cookies[ckIdx] >= greed[gIdx]) {
            ++happy;
            --ckIdx;
        }
    }
    return happy;
}

Identifying the Longest Wiggle Subsequence

A wiggle (oscillating) sequence is one where differences between consecutive elements alternate between positive and negative. Drawing the array as a line chart reveals peaks and valleys—three patterns must be handled:

• A strictly monotonic slope (no wiggle, count only endpoints).
• Flat segments within a slope (ignore repeated values to avoid false sign changes).
• Edge cases around the first and last element.

We track the previous difference (prevDiff) and current difference (currDiff). Every time the sign alternates (prevDiff >= 0 && currDiff < 0 or prevDiff <= 0 && currDiff > 0), we extend the sequence length and update prevDiff.

int wiggleMaxLength(vector<int>& sequence) {
    if (sequence.size() <= 1) return sequence.size();
    int length = 1;
    int prevDiff = 0;
    for (size_t i = 0; i < sequence.size() - 1; ++i) {
        int currDiff = sequence[i + 1] - sequence[i];
        if ((prevDiff >= 0 && currDiff < 0) || (prevDiff <= 0 && currDiff > 0)) {
            ++length;
            prevDiff = currDiff;
        }
    }
    return length;
}

Computing the Maximum Subarray Sum

A brute-force double loop works but misses an elegant greedy observation: whenever the running sum (currentSum) drops below zero, it cannot contribute positively to any future sum, so we reset it. The answer is tracked as the maximum value seen in currentSum throughout the iteration.

int maxSubArray(vector<int>& data) {
    int best = INT_MIN;
    int currentSum = 0;
    for (int value : data) {
        currentSum += value;
        if (currentSum > best) best = currentSum;
        if (currentSum < 0) currentSum = 0;
    }
    return best;
}

The resetting logic avoids the need to explicitly manage start and end positions; as soon as the accumulated sum becomes a liability, we conceptually shift the starting point forward.