Minimum cost of sorting an array of positive numbers

This is a Facebook interview problem which can be found at http://www.careercup.com/question?id=9333968.

Here is the problem statement from the site:
Given an array A of positive integers. Convert it to a sorted array with minimum cost. The only valid operation are: 
1) Decrement with cost = 1 
2) Delete an element completely from the array with cost = value of element

Most of array problem can be solved by 1) dynamic programming which usually has time complexity of O(n^2) or above, 2) sliding window which has time complexity of O(n). Then mixing with these two approach there will be various data structures or algorithms can be used, notably, binary search, stack, queue.

My first try is greedy algorithm:

Start from index at 0, using a sliding window, keep on expanding the window until find a the number which is larger than the previous number.
note the numbers in sliding window are sorted except the last one, supposed its value is k
using binary search to find the minimum index of the item larger than k in the sliding windows
now to make the sliding window completely sorted, we have two choices: 1) delete the last one, 2) decrease all of the items from the minimum index to end of sliding window to k. We can calculate the costs of these two choices, choose the one is minimum and then make change to the array

now we can expanding the sliding window again and repeat the above steps until reaching the end of array

However the above solution is not quite right, per Peng Li's comment below.

My second try is dynamic programming:

The idea is that the final sorted array will always end up with one of the original numbers appear in the array. then all of the larger numbers before this number will be decremented,  

dp(i, j), i is the index of the original array a[], j is the index of the sorted array b[] of unique numbers in the array 

 dp(i, j) = min(dp(i-1, 0), dp(i-1, 2), ... dp(i-1, j)) + cost_of_convert(a[i], b[j])

Final answer: min(dp(a.len-1, 0), dp(a.len-1, 1)..., dp(a.len-1, b.len-1)

public static int minSortCostDP(int[] nums){

Set<Integer> unique = new HashSet<Integer>();

for(int i:nums)

unique.add(i);

Set<Integer> sortedSet = new TreeSet<Integer>(unique);

Integer[] sorted = (Integer[]) sortedSet.toArray();

int lenA = nums.length,  lenB = sorted.length;

int[][] table = new int[lenA][lenB];

//first row

for(int col = 0; col<lenB; col++)

table[0][col] = Math.max(0, nums[0]-sorted[col]);

for(int row = 1; row<lenA; row++){

 for(int col = 0; col<lenB; col++){

  //either deletion or decrement

  int cost_of_convert = nums[row]>=sorted[col]? nums[row]-sorted[col]:nums[row];

  table[row][col] = Integer.MAX_VALUE;

  for(int k=0; k<=col; k++){

table[row][col] = Math.min(table[row-1][k]+cost_of_convert, table[row][col]);

  }

 }

}

int minCost = Integer.MAX_VALUE;

//last row

for(int col = 0; col<lenB; col++){

minCost = Math.min(table[lenA-1][col], minCost);

}

return minCost;

}

//Greedy algorithm approach which is not quite right

package org.blueocean;

public class FacebookQ {

//http://www.careercup.com/question?id=9333968

//find the min index of the item in array which large than k

public static int binarySearch(int[] nums, int start, int end, int k){

while(end-start>1){

int mid = (end+start)>>>1;

if(nums[mid]>k)

end = mid;

else

start = mid;

}

return nums[start]>k? start : end;

}

//greedy algorithm

public static int minSortCost(int[] nums){

int cost = 0;

int start = 0;

int end = 1;

int len = nums.length;

while(end<len){

while(end<len && nums[end]>=nums[end-1]){

end++;

}

if(end<len){

int index = binarySearch(nums, start, end-1, nums[end]);

int cost1 = nums[end];//deletion

int cost2 = 0;

for(int j = index; j<=end-1; j++)

cost2 += nums[j]-nums[end];//decrement

if(cost1<=cost2){

//delete item at index of end by shifting the rest of numbers after end

System.arraycopy(nums, end+1, nums, end, len-1-end);

len--;

cost += cost1;

}else{

for(int j = index; j<=end-1; j++)

nums[j] = nums[end];

cost += cost2;

}

}

end++;

}

return cost;

}

}