I have two arrays $$$A$$$ and $$$B$$$ of length $$$n$$$. I can make groups (not necessarily contiguous), the goal is to minimize $$$\sum_{i}max_{ai}*max_{bi}$$$ where $$$0 \leq i \leq n$$$ denotes group $$$i$$$. $$$max_{ai}$$$ denotes the maximum of $$$A[j]$$$s where $$$j$$$ belongs to group $$$i$$$. Similarly, $$$max_{bi}$$$ denotes the maximum of $$$B[j]$$$s where $$$j$$$ belongs to group $$$i$$$.

An example:

• $$$n = 3$$$ \ $$$A = [1, 10, 1000]$$$ \ $$$B = [1000, 10, 1]$$$
• Making three groups result in a score of $$$2100$$$.
• Taking everyone altogether results in a score of $$$10^6$$$.
• It's easy to see in this situation (I didn't detail the scores when having a group of 2) it's best to make three groups.

If we sort $$$A$$$ (and re-arrange the indices in $$$B$$$ accordingly of course), we could say that the problem is solvable with DP. Let $$$dp[i]$$$ be the best we could do if we only had $$$A[:i]$$$ and $$$B[:i]$$$ arrays ($$$i$$$ exluded).

I argue (see below for incomplete proof) this transition works: $$$dp[i] = min_j(dp[i], dp[j−1] + maxA⋅maxB)$$$. The minimum is taken over $$$j$$$ that goes from $$$1$$$ to $$$i$$$. If $$$j = 1$$$ it means we make one group (from $$$0$$$ to $$$i-1$$$). If $$$j = i$$$ that means the new member at index $$$i-1$$$ is on its own group. $$$maxA$$$ is the maximum of $$$A[l]$$$ for $$$j-1 \leq l \leq i-1$$$. Same goes for $$$maxB$$$.

Now, since the array is sorted, $$$maxA = A[i-1]$$$, therefore: $$$dp[i] = min_j(dp[i], dp[j−1] + A[i-1]*maxB$$$) (that doesn't actually matter here).

My argument for this transition is that, after sorting $$$A$$$ (and re-arranging the indices in $$$B$$$ accordingly of course), the groups have to be contiguous which is why the new member $$$i-1$$$ can only belong to a contiguous group starting at a $$$j-1$$$ with $$$1 \leq j \leq i$$$. E.g., if $$$n = 3$$$, then if $$$a_1 \leq a_2 \leq a_3$$$ then putting 1 and 3 together in a group and 2 on its own is always suboptimal. Quite easy to prove when $$$n = 3$$$:

Let's do a proof by contradiction. Let's assume putting 1 and 3 together in a group and 2 on its own is optimal. If $$$b_1 \leq b_2$$$, then we would always group 1 and 2 together because $$$a_2*b_2$$$ would be the cost of them together or the cost of 2 on its own. Similarly if $$$b_2 \leq b_3$$$ we would want to group 2 and 3. So we know that $$$b_1 > b_2 > b_3$$$ otherwise we would have a contradiction. But if $$$b_1 > b_2 > b_3$$$, the cost of group 1/3 together and 2 alone is $$$a_3*max(b_1, b_3) + a_2*b_2)$$$ which is $$$a_3*b_1 + a_2*b_2$$$ which is obviously greated than $$$a_3*b_1$$$ which is equal to $$$max(a_1, a_2, a_3)*max(b_1, b_2, b_3)$$$. So it would cost less to group everyone together. Hence contradiction.

How do I generalize the fact that the groups have to be contiguous now? Since it works on 3, it'd always work right? I don't know, I feel like I'm missing something and the DP transition relies on this assumption.

I hope it was clear, it's my first time asking a question like this here.