Need Help with a particular problem.

Revision en1, by Aspergillus, 2024-01-15 16:48:50

How do I calculate the length of longest subarray ending at index $$$i$$$ $$$(1 \leq i \leq N)$$$ with elements smaller than or equal to $$$A[i]$$$ in an array A of length N for each $$$i$$$? $$$(1 \leq N \leq 10^6).$$$

I have tried a few different approaches with two pointers, tried using the merge sort algorithm to find the lesser than or equal to elements before each element but every approach I tried have obvious flaws.

Can anyone please help me with this? I would appreciate a solution without the use of data structures like segment trees or BIT and such, as I am yet to learn about these.

Tags help me

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English Aspergillus 2024-01-15 16:48:50 627 Initial revision (published)