Let's swap

Y is alone too and has a permutation $p_1,p_2,...,p_n$ of numbers from $1$ to $n$.

Y thinks that a permutation $p_1,p_2,...,p_n$  beautifulness is defined as value of $\sum |p_i-i|,1\le i\le n$.

Y can swap two elements of the permutation at most once, what is the maximum beautifulness that Y can get?

Example:

Input:  n=5, arr[] = { 1, 4, 2, 3, 5 }
Output: 12

Approach

Java

public class LetSwap {
    public static void main(String args[]) {
        int n = 5;
        long result = 0;
        long curr = 0;
        int arr[] = { 1, 4, 2, 3, 5 };
        int p[] = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            p[i] = arr[i - 1];
            curr += Math.abs(p[i] - i);
        }
        result = curr;
        int[] dp1 = new int[n + 1];
        int[] dp2 = new int[n + 1];
        dp1[0] = Integer.MAX_VALUE;
        dp2[0] = Integer.MAX_VALUE;
        for (int i = 1; i <= n; i++) {
            if (p[i] >= i) {
                result = Math.max(result, curr + 2l * (i - dp1[i - 1]));
                result = Math.max(result, curr + 2l * (i - dp2[i - 1]));
            } else {
                result = Math.max(result, curr + 2l * (p[i] - dp1[Math.min(i - 1, p[i])]));
                result = Math.max(result, curr + 2l * (p[i] - dp2[Math.min(i - 1, p[i])]));
            }

            if (p[i] >= i)
                dp1[i] = Math.min(dp1[i - 1], p[i]);
            else
                dp1[i] = dp1[i - 1];

            if (p[i] <= i)
                dp2[i] = Math.min(dp2[i - 1], i);
            else
                dp2[i] = dp2[i - 1];
        }
        System.out.println(result);
    }

}