Shawn's Blog

class SummaryRanges {
    map<int, int> m;
public:
    SummaryRanges() {}
    
    void addNum(int val) {
        int left = val, right = val;
        for (auto it = m.lower_bound(val - 1); it != m.end() && it->second <= right + 1; m.erase(it++)) {
            int l = it->second, r = it->first;
            left = min(left, l), right = max(right, r);
        }
        m[right] = left;
    }
    
    vector<vector<int>> getIntervals() {
        vector<vector<int>> v;
        for (auto it = m.begin(); it != m.end(); ++it)
            v.push_back({it->second, it->first});
        return v;
    }
};

/**
 * Your SummaryRanges object will be instantiated and called as such:
 * SummaryRanges* obj = new SummaryRanges();
 * obj->addNum(val);
 * vector<vector<int>> param_2 = obj->getIntervals();
 */

class RangeModule {
    map<int, int> m;
public:
    RangeModule() {}
    
    void addRange(int left, int right) {
        for (auto it = m.lower_bound(left); it != m.end() && it->second <= right; m.erase(it++)) {
            int l = it->second, r = it->first;
            left = min(left, l), right = max(right, r);
        }
        m[right] = left;
    }
    
    bool queryRange(int left, int right) {
        auto it = m.lower_bound(left);
        return it != m.end() && it->second <= left && it->first >= right;
    }
    
    void removeRange(int left, int right) {
        for (auto it = m.lower_bound(left + 1); it != m.end() && it->second <= right;) {
            if (it->second < left) {
                m[left] = it->second;
            }
            if (it->first > right) {
                m[it->first] = right;
                break;
            } else m.erase(it++);
        }
    }
};

/**
 * Your RangeModule object will be instantiated and called as such:
 * RangeModule* obj = new RangeModule();
 * obj->addRange(left,right);
 * bool param_2 = obj->queryRange(left,right);
 * obj->removeRange(left,right);
 */

class CountIntervals {
    map<int, int> m;
    int cnt = 0;
public:
    CountIntervals() {}
    
    void add(int left, int right) {
        for (auto it = m.lower_bound(left); it != m.end() && it->second <= right; m.erase(it++)) {
            int l = it->second, r = it->first;
            left = min(left, l), right = max(right, r);
            cnt -= r - l + 1;
        }
        cnt += right - left + 1;
        m[right] = left;
    }
    
    int count() {
        return cnt;
    }
};

/**
 * Your CountIntervals object will be instantiated and called as such:
 * CountIntervals* obj = new CountIntervals();
 * obj->add(left,right);
 * int param_2 = obj->count();
 */

class Solution {
public:
    int kConcatenationMaxSum(vector<int>& arr, int k) {
        int n = arr.size(), sum = arr[0], maxSum = arr[0];
        int64_t total = accumulate(arr.begin(), arr.end(), 0), mod = 1e9 + 7;
        for (int i = 1; i < n * min(k, 2); ++i) {
            if (sum > 0) sum += arr[i % n];
            else sum = arr[i % n];
            maxSum = max(maxSum, sum);
        }
        return max<int64_t>({0, maxSum, total * max(0, k - 2) + maxSum}) % mod;
    }
};

class Solution {
public:
    int maximumSum(vector<int>& arr) {
        int n = arr.size(), deleted = 0, reserved = arr[0], ans = arr[0];
        for (int i = 1; i < n; ++i) {
            deleted = max(deleted + arr[i], reserved);
            reserved = max(reserved + arr[i], arr[i]);
            ans = max(ans, max(deleted, reserved));
        }
        return ans;
    }
};

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int minProduct = nums[0], maxProduct = nums[0], ans = nums[0];
        for (int i = 1; i < nums.size(); ++i) {
            int m1 = minProduct, m2 = maxProduct;
            maxProduct = max(max(nums[i], m1 * nums[i]), m2 * nums[i]);
            minProduct = min(min(nums[i], m1 * nums[i]), m2 * nums[i]);
            ans = max(ans, maxProduct);
        }
        return ans;
    }
};

class Solution {
public:
    int largestVariance(string s) {
        int ans = 0;
        unordered_set<char> unique(s.begin(), s.end());
        // go through each possibilities to find the ans.
        for (char a : unique)
            for (char b : unique) {
                if (a == b) continue;
                int var = 0, has_b = 0, first_b = 0;
                for (auto ch : s) {
                    // var is used to track the occurrences diff between "a" and "b".
                    if (ch == a) ++var;
                    else if (ch == b) {
                        has_b = true;
                        // we are having a leading "b" and now one more "b" with cnt(a) >= cnt(b),
                        // so we can cut the leading "b" for a better ans.
                        if (first_b && var >= 0) first_b = false;
                        // "--var < 0" indicates that we are having too many "b(s)" here,
                        // so we take this "b" as a fresh start.
                        else if (--var < 0) first_b = true, var = -1;
                    }
                    // update the ans if and only if "b" is within the substr.
                    ans = max(ans, has_b ? var : 0);
                }
            }
        return ans;
    }
};