[Algorithm]Hill

Given an array of integer elements
Your task is to

• write a function that finds the minimum value X that makes possible the following: generate a new array that is sorted in strictly ascending order by increasing or decreasing each of the elements of the initial array with integer values in the [0, X] range.
  • Example: Having the initial array [5, 4, 3, 2, 8] the minimum value for X is 3. Decrease the first element (5) by 3, decrease the second one (4) by 1, increase the third one (3) by 1, increase the forth one (2) by 3 and do nothing to the last one (8). In the end we obtain the array [2, 3, 4, 5, 8] which is sorted in strictly ascending order.
• print the result X to the standard output (stdout)

这一题乍看之下感觉不太好做，其实仔细分析一下还是比较简单的，我们首先定义distance：两个数之间的distance代表要让这两个数变成strictly ascending要在第二个数上加的最小值，也就是说对于两个数A[i]，A[j]，distance(i, j) = max(A[i] + (j - i) - A[j], 0)，distance永远大于等于0。所以这题就转化成了我们要求数组里的max distance，返回的时候我们返回(maxDis + 1) / 2。

为了在O(n)时间求出来我们依然要使用DP，globalMax[i]是到A[i]为止最大的distance，localMax[i]是到A[i]为止最大的distance，并且第二个数为A[i]。DP方程为：

• globalMax[i] = max(localMax[i], global[i - 1]);
• localMax[i] = max(localMax[i - 1] + A[i - 1] - A[i] + 1, A[i - 1] - A[i] + 1, 0)

我们可以把空间优化到常数，代码如下：

	class MyClass {
	public static void hill(Integer[] v) {
	// Write your code here
	// To print results to the standard output you can use System.out.println()
	// Example: System.out.println("Hello world!");
	if (v == null)
	return;
	int len = v.length;
	if (len < 2)
	return;
	int base = v[0], baseIndex = 0, maxDiff = 0;
	for (int i = 1; i < len; i++) {
	int diff = base + i - baseIndex - v[i];
	maxDiff = diff > maxDiff? diff: maxDiff;
	if (diff < 0) {
	base = v[i];
	baseIndex = i;
	}
	}
	System.out.println((maxDiff + 1) / 2);
	}
	}

view raw hill.java hosted with ❤ by GitHub