Maximizing Array Sum After K Negations

Given an integer array, we can perform K operations where each operation flips the sign of an element. The goal is to maximize the sum after exactly K operations.

Approach:

1. Sort the array by absolute values in descending order
2. Flip negative numbers first too maximize sum gains
3. If remaining operations are odd, flip the smallest absolute value element

class Solution {
    static bool absCompare(int x, int y) {
        return abs(x) > abs(y);
    }
    
public:
    int maxSumAfterNegations(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end(), absCompare);
        
        for (int i = 0; i < nums.size() && k > 0; i++) {
            if (nums[i] < 0) {
                nums[i] = -nums[i];
                k--;
            }
        }
        
        if (k % 2 == 1) {
            nums.back() = -nums.back();
        }
        
        return accumulate(nums.begin(), nums.end(), 0);
    }
};

Gas Station Problem

Determine if a circular route can be completed given gas stasions with available fuel and costs to travel between them.

Greedy Approach:

• Track cumulative fuel balance
• Reset starting point when balance becomes negative
• Total fuel must exceed total cost for solution to exist

class Solution {
public:
    int findStartingStation(vector<int>& fuel, vector<int>& cost) {
        int currentBalance = 0;
        int totalBalance = 0;
        int startIndex = 0;
        
        for (int i = 0; i < fuel.size(); i++) {
            int net = fuel[i] - cost[i];
            currentBalance += net;
            totalBalance += net;
            
            if (currentBalance < 0) {
                startIndex = i + 1;
                currentBalance = 0;
            }
        }
        
        return totalBalance >= 0 ? startIndex : -1;
    }
};

Candy Distribution Problem

Distribute candies to chilrden such that higher-rated children get more candies than their immediate neighbors.

Two-pass Strategy:

1. Left to right: Ensure right neighbors get more if rating is higher
2. Right to left: Ensure left neighbors get more if rating is higher
3. Take maximum from both passes

class Solution {
public:
    int minCandies(vector<int>& ratings) {
        vector<int> candies(ratings.size(), 1);
        
        // Left to right pass
        for (int i = 1; i < ratings.size(); i++) {
            if (ratings[i] > ratings[i - 1]) {
                candies[i] = candies[i - 1] + 1;
            }
        }
        
        // Right to left pass
        for (int i = ratings.size() - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1]) {
                candies[i] = max(candies[i], candies[i + 1] + 1);
            }
        }
        
        return accumulate(candies.begin(), candies.end(), 0);
    }
};