class Solution {
public:
    vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {
        int m = nums1.size(), n = nums2.size();
        vector<int> result;
        for (int i = max(0, k-n); i <= min(k, m); i++) {
            result = max(result, mergeVector(maxVector(nums1, i), maxVector(nums2, k-i)));
        }
        return result;
    }
    
    vector<int> maxVector(vector<int> nums, int k) {
        int drop = nums.size() - k;
        vector<int> result;
        for (int num : nums) {
            while (drop && result.size() && result.back() < num) { result.pop_back(); --drop; }
            result.push_back(num);
        }
        result.resize(k);
        return result;
    }
    
    vector<int> mergeVector(vector<int> nums1, vector<int> nums2) {
        vector<int> result;
        while (nums1.size() + nums2.size()) {
            vector<int> &temp = nums1 > nums2 ? nums1 : nums2;
            result.push_back(temp[0]);
            temp.erase(temp.begin());
        }
        return result;
    }
};

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        if (heights.size() == 0) return 0;
        heights.push_back(0);
        int result = 0;
        stack<int> st;
        for (int i = 0; i < heights.size(); i++) {
            if (st.empty() || heights[st.top()] <= heights[i]) st.push(i);
            else {
                while (!st.empty() && heights[st.top()] > heights[i]) {
                    int cur = heights[st.top()];
                    st.pop();
                    int len = st.empty() ? i : i - st.top() - 1;
                    result = max(result, len * cur);
                }
                st.push(i);
            }
        }
        return result;
    }
};

class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        /** largest rectangle based solution **/
        if(matrix.size()<=0 || matrix[0].size()<=0)
            return 0;
        int m=matrix.size();
        int n=matrix[0].size()+1;
        int h=0, w=0, result=0;
        vector<int> height(n, 0);
        for(int i=0; i<m; i++){
            stack<int> st;
            for(int j=0; j<n; j++){
                /** update the current row ended height array **/
                if(matrix[i][j]=='1')  height[j]+=1;
                else height[j]=0;
                /** use the histogram-max-rectangle-module **/
                if (st.empty() || height[st.top()] <= height[i]) st.push(i);
                else {
                    while(!st.empty() && height[st.top()]>=height[j]){
                        h=height[st.top()];
                        st.pop();
                        w=st.empty() ? j:j-st.top()-1;
                        if(h*w>result) result=h*w;
                    }
                    st.push(j);
                }
            }
        }
        return result;
    }
};

class Solution {
public:
    int minCut(string s) {
        int n = s.size();
        vector<vector<bool>> is_palindrome(n, vector<bool>(n, false));
        vector<int> dp(n, n);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= i; j++) {
                if (s[i] == s[j] && (i-j < 2 || is_palindrome[j+1][i-1])) {
                    is_palindrome[j][i] = true;
                    if (is_palindrome[0][i]) dp[i] = 0;
                    else {
                        dp[i] = min(dp[i], dp[j-1] + 1);
                    }
                }
            }
        }
        return dp[n-1];
    }
};