Fundamentals of Greedy Algorithms

The core principle of a greedy algorithm is to make the locally optimal choice at each stage with the hope that these local choices will lead to a globally optimal solution. For instance, when counting currency, taking the largest denomination possible at each step ensures the minimum number of notes.

Unlike dynamic programming, there is no rigid framework for solving problems with a greedy approach. The primary challenge lies in determining whether a problem is suitable for this strategy. Usually, one must simulate the problem: if a counter-example cannot be found where local optimization fails to produce a global optimum, a greedy strategy is worth attempting.

In professional or interview settings, rigorous mathematical proofs (such as mathematical induction or proof by contradiction) are rarely required. It is generally sufficient to provide a logical explanation or pass the test cases.

Problem I: Assign Cookies

Objective: Maximize the number of content children. Each child has a greed factor, and each cookie has a size. A child is content if the cookie size is greater than or equal to their greed factor.

Strategy: Use the largest available cookies to satisfy the children with the largest greed factors. Sorting both arrays allows us to efficiently match resources using a two-pointer technique.

class Solution {
public:
    int findContentChildren(vector<int>& greedFactors, vector<int>& cookieSizes) {
        sort(greedFactors.begin(), greedFactors.end());
        sort(cookieSizes.begin(), cookieSizes.end());
        
        int childIndex = greedFactors.size() - 1;
        int cookieIndex = cookieSizes.size() - 1;
        int satisfiedCount = 0;
        
        while (childIndex >= 0 && cookieIndex >= 0) {
            if (cookieSizes[cookieIndex] >= greedFactors[childIndex]) {
                // Cookie can satisfy the child
                satisfiedCount++;
                cookieIndex--;
                childIndex--;
            } else {
                // Cookie too small, try to satisfy a less greedy child
                childIndex--;
            }
        }
        return satisfiedCount;
    }
};

Problem II: Wiggle Subsequence

Objective: Find the length of the longest wiggle subsequence, where the differences between successive numbers alternate strictly between positive and negative.

Strategy: Instead of deleting elements, we count the number of "peaks" and "valleys." A peak occurs when the sequence changes from increasing to decreasing, and a valley occurs when it changes from decreasing to increasing. We must handle flat sequences (difference of 0) carefully to avoid counting false fluctuations.

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        if (nums.size() < 2) return nums.size();
        
        int prevDiff = 0;
        int currentDiff = 0;
        int length = 1; // A single element is a wiggle sequence of length 1
        
        for (int i = 0; i < nums.size() - 1; i++) {
            currentDiff = nums[i + 1] - nums[i];
            
            // Detect a valid peak or trough, treating flat starts appropriately
            if ((prevDiff <= 0 && currentDiff > 0) || 
                (prevDiff >= 0 && currentDiff < 0)) {
                length++;
                prevDiff = currentDiff; // Only update difference on a valid turn
            }
        }
        return length;
    }
};

Problem III: Maximum Subarray

Objective: Find the contiguous subarray within a one-dimensional array of numbers which has the largest sum.

Strategy: Iterate through the array while maintaining a running sum. If the running sum becomes negative, it is detrimental to any subsequent elements added to it. Therefore, we reset the running sum to zero. We continuously track the maximum sum encountered during this process.

class Solution {
public:
    int maxSubArray(vector<int>& data) {
        int maxSum = data[0];
        int runningSum = 0;
        
        for (int value : data) {
            runningSum += value;
            
            // Update the maximum found so far
            if (runningSum > maxSum) {
                maxSum = runningSum;
            }
            
            // If the running sum is negative, reset it for the next element
            if (runningSum < 0) {
                runningSum = 0;
            }
        }
        return maxSum;
    }
};

Note: The initialization of maxSum with data[0] (or the smallest possible integer) ensures the algorithm handles arrays containing only negative numbers correctly. The core logic relies on the fact that a negative prefix will never contribute positively to a maximum subarray sum.