Pair of Sequences

Consider each column $k$ independently.

For two sequences $P_i,P_j$, the value $f(P_i,P_j)$ is the maximum of $P_{i,k}+P_{j,k}$ over all columns $k$. For a fixed column $k$, the largest possible sum is obtained by choosing the two largest values in that column from two distinct sequences.

While reading the input, maintain the largest and second largest values for each column, together with the indices of the sequences where they appear.

After reading the input, check every column $k$. The pair corresponding to the largest sum of the two largest values in a column is an optimal answer.

For correctness, fix any pair $P_i,P_j$ and any column $k$. The value $P_{i,k}+P_{j,k}$ cannot exceed the sum of the two largest values in column . Hence no pair can achieve a value larger than the best candidate we check. Conversely, the two sequences chosen from the best column actually achieve that candidate value, so the answer is optimal.

The time complexity is $O(NM)$, and the memory complexity is $O(N)$.