Insertion Sort Variant

Problem Statement

We have an array A and we want to sort it in non-decreasing order. The only allowable operation is to move one element of the array into any other place (before all elements, after all elements or between any two adjacent elements). The cost of the single operation is equal to the value of the moved element. We want to minimize the total cost of sorting the array.

For example, we have an array {7, 1, 2, 3}. We can sort it by moving 7 from the head to the tail. But the cost of this operation is 7 which is not optimal. The optimal sorting algorithm is to consecutively move 1, 2 and 3 to the proper places before 7. The total cost of these three movements will be 1+2+3=6, which is less than 7.

You will be given a int[] theArray. Return the minimal total cost required to sort the array.

http://community.topcoder.com/stat?c=problem_statement&pm=4844

public class MinimalCostSort {

	public static int calcMinimalCost(int[] arr) {
		int[] f = new int[arr.length];
		int res = 0;
		for (int i = 0; i < arr.length; i++) {
			f[i] = arr[i];
			for (int j = 0; j < i; j++) {
				if (arr[j] <= arr[i])
					f[i] = Math.max(f[i], f[j] + arr[i]);
			}
			res = Math.max(res, f[i]);
		}
		res = -res;
		for (int i = 0; i < arr.length; i++)
			res += arr[i];
		return res;
	}

	public static void main(String[] args) {

		int a[] = {6, 4, 5, 3, 8, 2, 7, 2, 11, 2, 2};
		int b[] = {8, 2, 6, 5, 1, 4};

		System.out.println("Minimal cost is "+calcMinimalCost(a));
		System.out.println("Minimal cost is "+calcMinimalCost(b));
	}

}