title: Grouping numbers in a list
body: <p>I came across the following question,</p>
  
  <p>You are given an array A of n elements. These elements are now added to a new list L which is initially empty , in a certain order based on the given q queries.</p>
  
  <ul>
  <li>In each query you are given an integer i that corresponds to A[i] in the array A. This means that you have to add the element A[i] to the list L.</li>
  <li>After each element is added to the list L, make groups among the elements in the list L. Two elements will be in same group if their indexes in the array A are consecutive.</li>
  <li>For each group we define the group’s value as <strong>axb</strong> where a is the largest value in that group and b is the size of that group.</li>
  </ul>
  
  <p>Print the maximum group value among all the groups that are formed after each element is added to the list L.</p>
  
  <p>My approach was to use a <code>map&lt;int,vector&lt;int&gt;&gt;</code> where key is the group number and value is a vector containing group size, max. of group. I also had an array g  and g[i] indicated group number of a[i], -1 if it is not in any group. The code below is a part of my implementation, but I'm sure there are better ways to solve this question as this solution of mine gave TLE and WA in some cases,and I can't seem to figure out the correct approach. Pls suggest optimal way to solve this.</p>
  
  <pre><code>int g[a.size()+2];       //+2 because queries start with index 1, and g[i] corresponds to a[i-1] 
  for(int i=0;i&lt;a.size()+2;i++)
      g[i]=-1;
  int gno=1;
  map&lt;int,vector&lt;int&gt; &gt; m;
  vector&lt;int&gt; ans;
  int mx=0;
  for(unsigned int i=0;i&lt;queries.size();i++){
      int q = queries[i];
      if(g[q-1]==-1 &amp;&amp; g[q+1]==-1){
        //create new group with current eleent as first element
          g[q] = gno;        //gno is the group number.
          vector&lt;int&gt; v;
  
          v.push_back(1);
          v.push_back(a[q-1]);
          m[gno]=v;
          mx = max(mx,m[gno][0]*m[gno][1]);
          gno++;
      }
      else if(g[q-1]!=-1 &amp;&amp; g[q+1]==-1){
        //join current element to left group
          g[q] = g[q-1];
          m[g[q]][0]++;
          m[g[q]][1] = max(m[g[q]][1],a[q-1]);
          mx = max(mx,m[g[q]][0]*m[g[q]][1]);
      }
      else if(g[q-1]==-1 &amp;&amp; g[q+1]!=-1){
        //join current element to right group
          g[q] = g[q+1];
          m[g[q]][0]++;
          m[g[q]][1] = max(m[g[q]][1],a[q-1]);
          mx = max(mx,m[g[q]][0]*m[g[q]][1]);
      }
      else{
         //join both groups to left and right
          g[q]=g[q-1];
          int g1 = g[q];
          int i;
          m[g[q]][0] += 1 + m[g[q+1]][0];
          m[g[q]][1] = max(m[g[q]][1],max(a[q-1],m[g[q+1]][1]));
          for(i=q+1;g[i]==g[i+1];i++){
              g[i]=g1;
          }
          g[i]=g1;
          mx = max(mx,m[g[q]][0]*m[g[q]][1]);
      }
      ans.push_back(mx);
  }
  </code></pre>
  
  <p>. </p>