@smac89 (about cs.stackexchange.com/questions/105808/…) Exactly, I don't think OP is asking for an ordering of the element of 𝑎. Please read my answer carefully, especially the formal formulation.

since the function is determined by that equality already.

Ok I see your edit, so what is the output of I(0) for example?

I(0) is the index t such that a(0)=b(t). I(k) is the index t such that a(k)=b(t).

@Apass.Jack Ok so how do you query the oracle? i.e. what are the inputs e and f? Are you assuming that E is ordered? Is that what you mean by "strict linear ordering"?

$e$ and $f$ are the input. (Hm, so I should have written "when input are $e$ and $f$") For example, given 1 and 3 to the oracle, the oracle can reply 1. Yes, a strict linear ordering on E means E is ordered.

The input to the oracle must be an ordered pair of elements each of which is in $E$. Given element $e$ and $f$, the oracle replies -1 if $e<f$. Given element $e$ and $f$, the oracle replies 0 if $e$ and $f$ are the same element. Given element $e$ and $f$, the oracle replies 1 if $e>f$.

@user3371603 (cs.stackexchange.com/questions/105758/…) "One way for computing 𝑑𝑝2[𝑚][𝑛] is to find the maximum value of 𝑑𝑝[𝑚−1][𝑥]+𝑓(𝑥) for 𝑥≤𝑛, where 𝑓(𝑥) means optimum value for finding largest (just one) rectangle between x-th and n-th bar. It seems that it has the complexity of 𝑂(𝑀𝑁^2). Is it a good way?" Yes, it is a good way.

Could somebody take a look at cs.stackexchange.com/a/105833/68251 ? I think this is a good idea, but I'm still not sure of a good way to approach finding this $g(k)$ function I am talking about. I have always done it by trial and error in the past, but a rigorous method would be super helpful.

Any thoughts/feedback would be greatly appreciated

Come join SE:AI for fun! (We're still technically beta, so run a slightly looser ship, and we embrace theoretical subjects, so long as the questions are well founded.)