Ohk so lets say that elements from 1 to i-1 and its opposite side n-i+1 to N are arranged in an order .So lets say N=6 ,i=2 so we consider that a[1]<a[2] and a[5]>a[6] and lets say that we know the minimum swaps required to do this arrangement ,then we can calculate it for i=3.
So dp[i][2] indicates the minimum number of swaps required to make array great for indices 1 to i and its opposite side ,dp[i][0] denotes minimum value if i and N-i+1 indices are not swapped ,similarly dp[i][1] denotes minimum value if i and N-i+1 are swapped.
So i want to calculate dp[3][0] ,i can use dp[2][0],dp[2][1] as since i know that now values upto 2 are arranged ,i just have to check for 1 pair of element(3,4).Now i need to check if i can use dp[2][0],so just see if a[2]>a[3] and a[4]>a[5],if it is then i can use dp[2][0],similaarly do for dp[2][1](however swap a[2],a[5] and then check)
Similarly we calculate dp[3][1] but now we swap a[3],a[4] and then check the same things,(we do 1+min(ā¦) as this swap contributes thaat 1)
@eugalt - The fact here is, the pattern followed by that case is different which cannot be handled by current algorithm. Plus, how many people were able to catch the case at first try? Not 20% I am sure
