今�Hの国の呵呵君: [Algorithm]Hill

今�Hの国の呵呵君: [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)

Read full article from 今�Hの国の呵呵君: [Algorithm]Hill