tldr; For any sequence the maximum length of a non-increasing subsequence is equal to the minimum number of increasing subsequences required to cover the sequence.
The minimum number of chains (aka 'the width') of a partially ordered set is the length of the longest 'antichain' in the partially ordered set. To apply this to your problem let [math]i <_p j[/math] be defined as [math]i < j[/math] and [math]a_i < a_j[/math].
You're looking for the longest 'antichain'; the largest subset of elements from your partially ordered set that are all mutually uncomparable. Suppose we have an antichain and we order it by index and look at the corresponding values of a. The values of a must be non-increasing, otherwise they would be comparable. Therefore the longest antichain is the longest non-increasing subsequence.
There's actually an extension of this result where you can find the maximum number of elements you can cover with any fixed number of increasing subsequences using the RSK algorithm.