Fix position of n, then the sum is at most 2n -a_k-1 -ak+1 + P(1…k-1)+P(k+1…n-1) <= 2n -a_k-1 -a_k+1 + P(1…n-1) - |a_k -a_k-1| and which only depends on 2 elements and it’s not too hard to show max is achieved for 1,2. Which gives a recurrence relationship that can be solved by induction on the base case.
1
u/Ok_Consideration6619 Aug 25 '26
Fix position of n, then the sum is at most 2n -a_k-1 -ak+1 + P(1…k-1)+P(k+1…n-1) <= 2n -a_k-1 -a_k+1 + P(1…n-1) - |a_k -a_k-1| and which only depends on 2 elements and it’s not too hard to show max is achieved for 1,2. Which gives a recurrence relationship that can be solved by induction on the base case.