title: Maximum Sum Elements in Range
body: <blockquote>
  <p>Given an array 'A' of size 'N' containing integers. You need to answer
  'Q' queries of type [ L R X Y ]. In each of the query you need to
  select at least 'X' elements and at most 'Y' elements from range 'L'
  to 'R' of the array 'A' such that their sum is maximum.</p>
  <p>Output the maximum sum achievable for each of the query.</p>
  <p><strong>Example :</strong></p>
  <pre><code>N = 5 
  A = [ 1, 2, -1, -2, 3 ]
  Q = [ [ 1, 3, 1, 2 ] , [ 3, 4, 1, 2 ] ]
  </code></pre>
  <p><em>Output</em> : <code>3, -1</code></p>
  <p><strong>Expanation :</strong></p>
  <p>For query 1, we select integers 1 and 2 to get the sum 3. This is the
  maximum sum achievable in the range index 1 to 3.</p>
  <p>For query 2, we need to select at least 1 element so we select -1 to
  get maximum sum -1.</p>
  <p><strong>Note :</strong></p>
  <p>The selected elements in the range L to R need not be consecutive. You can &gt; select subsequence of integers to maximise the sum.</p>
  <p><strong>Constraints :</strong></p>
  <pre><code>1&lt;=N&lt;=10^5
  1&lt;=Q&lt;=10^5
  -10^8 &lt;= A[i] &lt;= 10^8
  1&lt;=L&lt;=R&lt;=N
  1&lt;=X&lt;=Y&lt;=R-L+1
  </code></pre>
  </blockquote>
  <p>I tried to think of some approaches but could not find any algo for the above constraints. Any help/hint would be appreciated.</p>