Convert an Array into a Sorted Array with Minimum Cost

Problem: Given an array of positive integers, and you only have two operations : a) decrease an integer by k  with a cost of k; b) delete an integer with a cost of the value of that integer. Try to use these two operations to convert the array into a sorted array with minmum cost. For example, a[] = {5,4,7,3}, the optimal way is to decrease "5" by 1 and delete "3" with the total cost of 4 (1+3). The resulting sorted array is {4, 4, 7}.

Solution: Here I give a O(N^2) solution by using DP. The key data structure we need is dp[i] which records the minimum cost to covert a subarray a[0, i] into sorted array and the last element of the sorted array should be a[i].  For the example array a[] = {5,4,7,3}, dp[0] = 0, dp[1] = 1 (since we need to decrease "5" by 1), dp[2] = 1, dp[3] = 7. After we had filled up dp[], we need one more data structure: aggr[]. aggr[i] = a[0] + a[1] + ... + a[i]. Then the minmum cost to convert the whole array cost_min = min{dp[i] + aggr[N-1] - aggr[i]}. Here  "aggr[N-1] - aggr[i]" means the cost that we  delete all the elements with a subscript larger than i.

Then the key is to calculate dp[i]. There are several observations here:

1. if a[i] >=  a[j] (j<i),  we can construct a sorted array ended at a[i] by deleting a[j+1], a[j+2], ... , a[i-1] and then append a[i]. The cost of the resulting sorted array is dp[j] + the cost of deleting a[j+1], a[j+2], ... , a[i-1]. 
2. if a[i] < a[j], to have a[i] as the last element, we need to decrease a[j] by a[j] - a[i]. Moreover,  we may not stop at a[j] and we need to keep look backward until we found a a[m] such that a[m] <= a[i], then the cost of the resulting sorted array is dp[m+1] + ∑(a[k] - a[i]) where m<k<j. 
3. To compute dp[i], we need to look at all the j such that  j<i, depending on a[j] and a[i], we need to calculate the cost based on step 1 or 2. Then the minmum cost we encounter is the value of dp[i].

The code is as follow:

int min_convert_cost(int a[], int n)
{
    int dp[n];
    int aggr[n];

    aggr[0] = a[0];
    for(int i=1; i<n; i++)
        aggr[i] = aggr[i-1] + a[i];

    dp[0] = 0;
    for(int i=1; i<n; i++)
    {
       dp[i] = INT_MAX;
       for(int j=i-1; j>=0; j--)
       {
          int cost_i = 0;

          if(a[i] >= a[j])
          {
             cost_i = dp[j] + aggr[i-1] - aggr[j];
          }
          else
          {
              cost_i += aggr[i-1] - aggr[j];
              while(a[j]>a[i] && j >=0)
              {
                cost_i += a[j]-a[i];
                j--;
              }
              
              cost_i += dp[j+1];

          }
          if(cost_i < dp[i])
               dp[i] = cost_i;

       }
    }

   int min = INT_MAX;
   for(int i=0; i<n; i++)
   {
      int cost_i = dp[i] + aggr[n-1] - aggr[i];
      if(cost_i<min) min = cost_i;
   }

   return min;
}