Longest Encreasing Subsequence

The problem can be solved using a greedy approach by maintaining a sequence that represents the smallest possible tail value for all increasing subsequences of each length.

The key insight is that for any increasing subsequence, if we encounter a number that's smaller than the current tail of our sequence, we can replace the tail with this smaller number without affecting the length of the longest increasing subsequence. This allows us to maintain the optimal subsequence structure while scanning through the array.

The algorithm works by:

1. Initializing an empty list to store the tails of subsequences
2. Iterating through each number in the input array
3. If the current number is greater than the last element in our tails list, we append it
4. Otherwise, we find the first element in the tails list that's greater than or equal to the current number and replace it

To optimize the search for the replacement position, we can use binary search instead of linear search.

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        vector<int> tails;
        for (int num : nums) {
            if (tails.empty() || num > tails.back()) {
                tails.push_back(num);
            } else {
                int left = 0, right = tails.size() - 1;
                while (left < right) {
                    int mid = left + (right - left) / 2;
                    if (tails[mid] < num) {
                        left = mid + 1;
                    } else {
                        right = mid;
                    }
                }
                tails[left] = num;
            }
        }
        return tails.size();
    }
};

Best Time to Buy and Sell Stock

This problem can be efficiently solved using a greedy approach by tracking the minimum price encountered so far and calculating the maximum profit at each step.

The greedy strategy involves:

1. Initializing the minimum price as the first element
2. Iterating through the price array
3. At each step, calculating potential profit by subtracting current minimum from current price
4. Updating maximum profit if current profits greater
5. Updating minimum price if current price is lower

This approach ensures we only need a single pass through the array, achieving O(n) time complexity.

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if (prices.empty()) return 0;
        
        int minPrice = prices[0];
        int maxProfit = 0;
        
        for (size_t i = 1; i < prices.size(); ++i) {
            maxProfit = max(maxProfit, prices[i] - minPrice);
            minPrice = min(minPrice, prices[i]);
        }
        
        return maxProfit;
    }
};

Best Time to Buy and Sell Stock II

For this problem, we can use a greedy approach that captures all possible profits from increasing sequences.

The key observation is that we can sum up all positive differences between consecutive days. This is equivalent to buying at the start of every increasing sequence and selling at the end.

Two approaches can be used:

1. Two-pointer technique to identify increasing sequences
2. Simple iteration that adds positive differences between consecutive days

Both approaches achieve the same result with O(n) time complexity.

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int totalProfit = 0;
        int n = prices.size();
        
        for (int i = 1; i < n; ++i) {
            if (prices[i] > prices[i-1]) {
                totalProfit += prices[i] - prices[i-1];
            }
        }
        
        return totalProfit;
    }
};

Advantage Shuffle (Tian Ji Horse Racing)

This problem can be solved using a greedy strategy inspired by the classic Tian Ji horse racing story.

The approach involves:

1. Sorting both arrays
2. Using a strategy where we try to match our strongest remaining horse against the opponent's weakest horse that we can beat
3. If we can't win, we sacrifice our weakest horse against their strongest

The algorithm works by:

1. Sorting nums1 in ascending order
2. Creating an array of indices for nums2 sorted by their values
3. Using two pointers to match horses optimally

class Solution {
public:
    vector<int> advantageCount(vector<int>& A, vector<int>& B) {
        int n = A.size();
        vector<int> indices(n);
        vector<int> result(n);
        
        // Initialize indices array
        for (int i = 0; i < n; ++i) {
            indices[i] = i;
        }
        
        // Sort A
        sort(A.begin(), A.end());
        
        // Sort indices based on values in B
        sort(indices.begin(), indices.end(), [&](int i, int j) {
            return B[i] < B[j];
        });
        
        int left = 0, right = n - 1;
        for (int num : A) {
            if (num > B[indices[left]]) {
                result[indices[left++]] = num;
            } else {
                result[indices[right--]] = num;
            }
        }
        
        return result;
    }
};

Assign Cookies

This problem can be solved using a greedy approach similar to the Advantage Shuffle problem.

The strategy is:

1. Sort both the children's greed factor array and the cookie size array
2. Use two pointers to match cookies to children
3. Give the smallest cookie that can satisfy the current child's greed

The algorithm works by:

1. Sorting both arrays
2. Using two pointers to traverse both arrays
3. Counting satisfied children when a cookie can satisfy a child's greed

class Solution {
public:
    int findContentChildren(vector<int>& children, vector<int>& cookies) {
        sort(children.begin(), children.end());
        sort(cookies.begin(), cookies.end());
        
        int childIndex = 0, cookieIndex = 0;
        int satisfied = 0;
        int numChildren = children.size();
        int numCookies = cookies.size();
        
        while (childIndex < numChildren && cookieIndex < numCookies) {
            if (cookies[cookieIndex] >= children[childIndex]) {
                satisfied++;
                childIndex++;
            }
            cookieIndex++;
        }
        
        return satisfied;
    }
};