RIOPLATENSE 2019 Problem 3

In the dog dictionary the words are any sequence of letters $A$ and $U$ for example $AA$ , $UAU$ and $AUAU$ . For each word, your "profundity" will be the quantity of subwords we can obtain by the removal of some letters. For each positive integer $n$ , determine the largest "profundity" of word, in dog dictionary, can have with $n$ letters. Note: The word $AAUUA$ has "profundity" $14$ because your subwords are $A, U, AU, AA, UU, UA, AUU, UUA, AAU, AUA, AAA, AAUU, AAUA, AUUA$ .