bool isPalindrome(string s){
    int n=s.length();
    for(int i=0;i<n/2;i++)
        if(s[i]!=s[n-1-i])
            return 0;
    return 1;
}
void partition1(vector<vector<string> > &v,vector<string> &row,string &s,int l,int n){
    if(l==n){
        v.push_back(row);
        return;
    }
    string temp="";
    for(int i=l;i<n;i++){
        temp+=s[i];
        if(isPalindrome(temp)){
            row.push_back(temp);
            partition1(v,row,s,i+1,n);
            row.pop_back();
        }
    }
}
vector<vector<string> > Solution::partition(string A) {
  vector<vector<string> > ans;
  vector<string> row;
  partition1(ans,row,A,0,A.length());
  return ans;
}



vector<int> Solution::prevSmaller(vector<int> &A) {

    vector<int >sol(A.size(),-1);
    stack<int>st;
    int n=A.size();
    st.push(n-1);

    for(int i=n-2;i>=0;i--){
        int j=A[i];
        while(!st.empty()&&j<A[st.top()]){
            sol[st.top()]=j;
            st.pop();
        }
        st.push(i);
    }
    return sol;
}

int findMaxUtil(Node* root, int &res)
{
    //Base Case
    if (root == NULL)
        return 0;

    // l and r store maximum path sum going through left and
    // right child of root respectively
    int l = findMaxUtil(root->left,res);
    int r = findMaxUtil(root->right,res);

    // Max path for parent call of root. This path must
    // include at-most one child of root
    int max_single = max(max(l, r) + root->data, root->data);

    // Max Top represents the sum when the Node under
    // consideration is the root of the maxsum path and no
    // ancestors of root are there in max sum path
    int max_top = max(max_single, l + r + root->data);

    res = max(res, max_top); // Store the Maximum Result.

    return max_single;
}