Is there a better approach to this permutation problem

Правка en1, от ABalobanov, 2021-11-20 15:56:41

I came up with the problem and could think of only $$$O(Prt(n) * poly(n) * log(n))$$$ solution ($$$Prt(n)$$$ -- number of non-decreasing partitions of number $$$n$$$). Given $$$n$$$, find a permutation with maximum possible value of $$$\sum_{i = 1}^n \sum_{j = i}^n max(p_i, p_{i + 1}, ..., p_j)$$$. My solution works in $$$n <= 50$$$ (maybe more with precalc). Is it possible to solve it better?

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский ABalobanov 2021-11-20 15:56:41 427 Initial revision (published)