<p>Part 1.</p>
<p>I found the notation a little confusing. The variable <span class="math-container">$n$</span> has repeated in two places.</p>
<p>To rephrase the question.</p>
<p>Input: A list of real numbers <span class="math-container">$[x_0, ..., x_n]$</span></p>
<p>Output: A list of integers <span class="math-container">$[d_0, ... , d_n]$</span> where <span class="math-container">$d_i$</span> is the largest <span class="math-container">$m\in\{1,\dots,i\}$</span> such that
<span class="math-container">$$
x_i\geq x_{i-1}, x_{i-2},\dots,x_{i-m}
$$</span></p>
<p>Part 2.</p>
<p>Using a stack I believe this can be achieved in linear time.</p>
<p>If <span class="math-container">$input[i] &lt; input[j]$</span> for any <span class="math-container">$i &lt; j$</span>, then for any index <span class="math-container">$i&lt;j&lt;k$</span> which is trying to update the <span class="math-container">$output[k]$</span> the value of <span class="math-container">$input[i]$</span> does not matter. If <span class="math-container">$input[k]&gt;input[j]$</span> then <span class="math-container">$input[k]&gt;input[i]$</span>. A stack can maintain this information well.</p>
<p>Below is a pseudo-code for the same.</p>
<pre><code>fn compute(input)
  stack = []
  output = []
  for i = 1:n
      while not stack.empty() and stack.top()[&quot;value&quot;] &lt; input[i]
        stack.pop()
      end
      if stack.empty()
        output.push(i) # Can go back all the way
      else
        output.push(i-stack.top()[&quot;index&quot;]) 
      end
      stack.push([{&quot;index&quot;:i, &quot;value&quot;:input[i]}]) # Push pair index,value
  end
  return output
end
</code></pre>

CC BY-SA 4.0
2023-07-13T19:07:28.523Z
2023-07-13T21:07:55.807Z
2023-07-13T21:07:55.807Z
Jarus
<p>Input: A list of real numbers <span class="math-container">$[x_0, ..., x_n]$</span></p>
<p>Output: A list of integers <span class="math-container">$[d_0, ... , d_n]$</span> where <span class="math-container">$d_i$</span> is the largest <span class="math-container">$d\in\{1,\dots,i\}$</span> such that
<span class="math-container">$$
x_i\geq x_{i-1}, x_{i-2},\dots,x_{i-d}
$$</span></p>
<p>In other words, <span class="math-container">$d_i$</span> says how far one can go backwards from <span class="math-container">$x_i$</span> without finding a larger element in the list.</p>
<p>Question 1: Is there a more compact or understandable way for the precise formulation?</p>
<p>Question 2: What is a good algorithm producing Output from Input?</p>

CC BY-SA 4.0
2023-07-17T09:33:09.247Z
Could you share some information about the application of such a problem? 
This question looks like an undergraduate programming exercise, which would not be adequate for cstheory SE ("Theoretical Computer Science - Stack Exchange is a question and answer site for professional researchers in theoretical computer science and related fields." https://cstheory.stackexchange.com/tour). If it is not, sharing some information about where it comes from would motivate your peers to work on it. If it is, maybe you should ask on a more adequate stack exchange channel, like https://cs.stackexchange.com/t
J.y B.y
<sorting>
Algorithm for comparing list elements backwards
loop_orange
# Algorithm for comparing list elements backwards

(Asked by: username_0 on 2023-07-12)

Input: A list of real numbers $[x\_0, ..., x\_n]$

Output: A list of integers $[d\_0, ... , d\_n]$ where $d\_i$ is the largest $d\in\{1,\dots,i\}$ such that
$$
x\_i\geq x\_{i-1}, x\_{i-2},\dots,x\_{i-d}
$$

In other words, $d\_i$ says how far one can go backwards from $x\_i$ without finding a larger element in the list.

Question 1: Is there a more compact or understandable way for the precise formulation?

Question 2: What is a good algorithm producing Output from Input?

**Tags:** sorting
> **Comments:**
> **username_1**: Could you share some information about the application of such a problem?  This question looks like an undergraduate programming exercise, which would not be adequate for cstheory SE ("Theoretical Computer Science - Stack Exchange is a question and answer site for professional researchers in theoretical computer science and related fields." https://cstheory.stackexchange.com/tour). If it is not, sharing some information about where it comes from would motivate your peers to work on it. If it is, maybe you should ask on a more adequate stack exchange channel, like https://cs.stackexchange.com/t  

---

## 1 answers

### Answer by username_2 on 2023-07-13. Score: 1 | Accepted answer

Part 1.
I found the notation a little confusing. The variable $n$ has repeated in two places.
To rephrase the question.
Input: A list of real numbers $[x_0, ..., x_n]$
Output: A list of integers $[d_0, ... , d_n]$ where $d_i$ is the largest $m\in\{1,\dots,i\}$ such that
$$
x_i\geq x_{i-1}, x_{i-2},\dots,x_{i-m}
$$
Part 2.
Using a stack I believe this can be achieved in linear time.
If $input[i] < input[j]$ for any $i < j$, then for any index $i which is trying to update the $output[k]$ the value of $input[i]$ does not matter. If $input[k]>input[j]$ then $input[k]>input[i]$. A stack can maintain this information well.
Below is a pseudo-code for the same.
fn compute(input)
  stack = []
  output = []
  for i = 1:n
      while not stack.empty() and stack.top()["value"] < input[i]
        stack.pop()
      end
      if stack.empty()
        output.push(i) # Can go back all the way
      else
        output.push(i-stack.top()["index"]) 
      end
      stack.push([{"index":i, "value":input[i]}]) # Push pair index,value
  end
  return output
end


---

