title: sum of maximum element of sliding window of length K
body: <p>Recently I got stuck in a problem. The part of algorithm requires to compute sum of maximum element of sliding windows of length <strong>K</strong>. Where <strong>K</strong> ranges from <strong><em>1&lt;=K&lt;=N</em></strong> (N length of an array).
  <br>
  <br>
  Example if I have an array A as <code>5,3,12,4</code><br>
  Sliding window of length 1: <code>5 + 3 + 12 + 4 = 24</code><br>
  Sliding window of length 2: <code>5 + 12 + 12 = 29</code><br>
  Sliding window of length 3: <code>12 + 12 = 24</code><br>
  Sliding window of length 4: <code>12</code><br>
  <br>
  <code>Final answer is 24,29,24,12</code>.<br>
  <br>
  I have tried to this <strong>O(N^2)</strong>. For each sliding window of length <strong>K</strong>, I can calculate the maximum in O(N). Since K is upto N. Therefore, overall complexity turns out to be <strong>O(N^2)</strong>.<br>
  I am looking for <strong>O(N)</strong> or <strong>O(NlogN)</strong> or something similar to this algorithm as N maybe upto 10^5. <br>
  <strong><em>Note:</strong> Elements in array can be as large as <strong>10^9</em></strong> so output the final answer as modulo <em>10^9+7</em>
  <br><br>
  <strong><em>EDIT: What I actually want to find answer for each and every value of K (i.e. from 0 to N) in overall linear time or in O(NlogN) not in O(KN) or O(KNlogN) where K={1,2,3,.... N}</em></strong></p>