I recently encountered a problem which states : There is an array A which contains n integers. In one operation we can swap Ai with one of its neighbours i.e., swap(Ai,Ai+1) or swap(Ai,Ai-1) provided any element in the array can be swapped atmax once. After doing some optimal number of operations, we have to find the max value of summation of i*Ai for i = 1 to n.
For ex — A : [2,1,4,3] n = 4
Ans : 30 Swap elements at index 1,2 and elements at 3,4 that gives us the final array as [1,2,3,4]. The sum is 1*1 + 2*2 + 3*3 + 4*4 = 1+4+9+16 = 30
Can someone help me with the ideas to solve this problem ?
is there any link of this problem?
if i swap Ai with Ai+1 does that mean i cant swap Ai+2 with Ai+1 ?
since Ai+1 swapped.
i haven't given it alot of thought but i think the idea of merge sort might work for this problem(ofc not the usual merge sort you will have to change somethings in it)
yes, as it was noticed in comment, you can swap each element only once
Constraints??
what about just swaping to the right the biggest $$$a_i$$$ you didn't swap so far? Any countercase?
Can solve using dp.
$$$\text{dp}[i]$$$ denotes max value for prefix upto $$$i$$$. Transitions are simple, if you swap you get $$$\text{dp}[i - 2] + (i - 1)\cdot\text{a}[i] + i\cdot\text{a}[i - 1]$$$, if you don't swap you get $$$\text{dp}[i - 1] + i\cdot\text{a}[i]$$$.
$$$\text{dp}[i]$$$ is the maximum of these two values. Answer is $$$\text{dp}[n]$$$. Note that I've 1-indexed everything for brevity.