CareerCup

Any help using Longest Increasing subsequence and then pointing those elements which are not in that LIS and then either:
1. decrement the to a value equal to their leftside or rightside?
2. delete it
which ever is minimal?

Check out the DP solution given here. Seems correct to me.
shashank7s. blogspot. com/2011/05/ wap-to-find-minimum-value-in-window-of . html

I have a O(n^2) solution to it. Though I guess that it can be improved to O(nlogn) somehow, I did not figure it out.
My method is DP. For your testing purpose, I copy the whole code to here. I will very briefly explain the logic later.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef vector<int> Array;
int arrange (Array arr)
{
	arr.push_back(*max_element(arr.begin(), arr.end()));
	Array cost_arr(arr.size());
	for (int i = 0; i < arr.size(); ++i)
	{
		int cur_extra_cost = 0; 
		int cur_upper_bound = arr[i], cur_lower_bound = 0;
		int cur_min_cost = unsigned(-1)>>1;
		for (int j = i - 1; j >= 0; --j)
		{
			if (arr[j] > cur_upper_bound)
			{
				cur_extra_cost += arr[j] - cur_upper_bound;
			}else if (arr[j] <= cur_lower_bound)
			{
				cur_extra_cost += arr[j];
			}else{
				int cur_cost = cur_extra_cost + cost_arr[j];
				cur_min_cost = cur_min_cost > cur_cost ? cur_cost : cur_min_cost;
				cur_extra_cost += arr[j];
				cur_lower_bound = arr[j];
			}
			
		}
		cur_min_cost = cur_min_cost > cur_extra_cost ? cur_extra_cost : cur_min_cost;
		cost_arr[i] = cur_min_cost;
	}
	return cost_arr[cost_arr.size() - 1];
	
}

int main()
{
	int arr[] = {7, 5, 9, 3, 1, 8, 6};
	//int arr[] = {7, 15, 19, 23, 31, 38, 46};
	cout<<arrange(Array(arr, arr + sizeof(arr)/sizeof(int)));
}

The idea is: to compute cost_arr[i], you need to know all potential contributors. I will give a example.
7 2 5 2 8 3 1 6.
To compute cost_arr[7] (for 6), we nee to know these numbers:
5 3 1.
These numbers are computed in this way:
Eliminate all numbers greater than 6 before 6. we get: 2 5 2 3 1.
Then from RIGHT to LEFT, find the increasing sequence: 5 3 1
That's it.
cost_arr[indexof(6)] = min {
cost_arr[indexof(1)] + cost_between(indexof(1), indexof(6)) ,
cost_arr[indexof(3)] + cost_between(indexof(3), indexof(6)) ,
cost_arr[indexof(5)] + cost_between(indexof(5), indexof(6))
}
Whats the final answer.
Still using 7 2 5 2 8 3 1 6.
The final answer is from cost_arr value at these numbers:
8 6
These numbers are computed in this way:
Find from the very RIGHT the increasing sequence:
8 6
final_ans = min{cost_arr[indexof(8)] , cost_arr[indexof(6)]}
It is equivalent to compute cost_arr[last_index] for this sequence:
7 2 5 2 8 3 1 6 INFINITY

That's how it works. I do not want to try to prove its correctness, but we can see its correctness through how it works.

I think the greedy strategy will work here.
Iterate from left to right.
For an element at index i, if there's an element at index j(j>i) with value(j)<value(i) , make value(i) = value(j). [cost incements by value(i) - value(j))

Worst case running time O(n^2)
Segment tree can reduce this to O(nlgn).

*correct the statment value(i) = value(j) as value(i) = min(value(j)) for all j>i

Wait I think I got it

1.Start from the last of the array (traverse array in reverse direction)
  and put the last element in stack S1.
2.For all element a[i],
  2.1 Till S1 is not empty or S1.top is lower than a[i], keep popping from S1 and push into Queue Q1.
  2.2 If S2 is empty,then simply push a[i] into S1 (no element to the right of a[i] is less than it)  
  2.3 Otherwise There are two options.
	2.3.1 Cost1: For deleting all the elements in the array which are in Q1.
	2.3.2 or, Cost2: For reducing a[i] by k, where k=a[i]-Q1.top
  Empty Q1.
  2.4 Recursively call with either of the state and return whichever has minimum cost.

I now thw recursive call for lookahead with both the state make the solution exponential,
but I think somehow the two cost definition can be converted into DP solution.
Someone help..

OK..I used all that stack and queue trying to do O(n) solution but couldn't,

Here is O(n^2) solution.

Global Cost=0
1. Start traversing from the end in reverse direction.
2. For each element a[i]
	2.1 Traverse to its right till a[i] is grater than the travered element
   	    Lets say u reached j. keep the sum1 of all elements from a[i+1] to a[j]
	2.2 If sum1=0, continue with the next iteration(step 2) for next left element.
	    Else go to step 2.3
	2.3 Sum2=0
	    Traverse to its left till a[0], and for all these a[k], 
	    if a[i+1]<a[k], Sum2+=a[k]-a[i+1]
	2.4 If sum1<sum2
	    Global Cost+=sum1 (delete elements from a[i+1] to a[j])
	    else Global Cost+=(a[i]-a[i+1]) (decrement a[i] to the value of a[i+1])

For each element sum1 finds the cost of deleting all elements smaller than this and right to it.
and sum2 finds the cost, if this number is reduced to the smaller number next to it, then watever
extra cost we will have to add for the elements to the left of it, which now have to be decreased.

{3,2,4,1}

Start with 1, since there is no element smaller in right of it, nothing to do.
Start with 4

there are two options, delete 1 or decrement 4 to 1
option 1: delete 1,   cost=1
option 2: If we decrement 4 to 1, we will also have to decrement all the elements 
          to the left of 4 to 1 in future.
	  so total cost=(4-1)+(2-1)+(3-1)=6
So we will take option 1 and delete 1. Global Cost=1.

Start with 2, there is no element smaller in right of it, nothing to do.
Start with 3

there are two options, delete 2 or decrement 3 to 2
option 1:delete 2, cost=2
option 2: decrement 3 to 2 (no element in the left of 3 to be considered in future)
          so total cost=3-2=1
So we will take option 2. Gloval cost=1+1=2

return global cost=2.

@XYZ the solution you posted uses greedy ans is incorrect. Try it on {5, 3, 5, 3}. The correct way to solve this is DP.

I got an DP in N^2...
It is easy to notice that your maximum value of the solution will be A[i] where 'i' is an index from 0 to n-1;
You DP[i][j] must says the minimum cost considering the solution till n, where the maximum value has the same value of the index[j];
And j >= i
So:
if A[i] <= A[j]:
then
DP[i][j] = min(A[i]+ DP[i-1][j], DP[i-1][i]);
else
DP[i][j] = A[i]-A[j] + DP[i-1][j];
When A[i] <= A[j] you need to notice that you can continue with A[i] at your solution, or you can erase A[i] and then maybe it will be good for you...

It has a greedy approach. Suppose you have sorted till i, you can add ith element by either deleting it or making the first i-1 element ai - (i-1),ai-(i-2) and so on.

Use DP. The following expression seems to work:

A is the input array.
OPT[i] is the optimal cost to generate a sorted array after having looked at the array elements from 0 to i.

OPT[i] = A[i-1]       if (A[i] >= A[i-1]) else:
         min (
               (OPT(i-i) + A[i]), 
               (OPT[i-1] + (A[0]+A[1]+...A[i-1] - (i-1)*A[i])) 
             )

The first expression is the cost of deleting the element at position i. The second expression is the cost of decrementing all the elements from 0 to i-1 to make them equal to A[i].

This approach requires only one traversal of the array. You can keep track of A[0]+A[1]+...A[i-1] in a variable as the array A is traversed.

DP problem. can be solved in O(n*n).

#include <iostream>
using namespace std;

int main()
{
	int f[100];
	int newA[100];

	int a[100] = {3, 2, 4, 1};

	int n = 4;

	a[n] = INT_MAX;
	f[n] = 0;
	newA[n] = INT_MAX;

	for(int i = n - 1; i >= 0; i--)
	{
		f[i] = INT_MAX;
		for(int j = i + 1; j <= n; j++)
			if (a[i] > newA[j])
			{
				int sum = 0;
				for(int k = i + 1; k < j; k++)
					sum += a[k];

				if (f[j] + sum + a[i] - newA[j] < f[i])
				{
					f[i] = f[j] + sum + a[i] - newA[j];
					newA[i] = newA[j];
				}
			}
			else
			{
				int sum = 0;
				for(int k = i + 1; k < j; k++)
					sum += a[k];

				if (f[j] + sum < f[i])
				{
					f[i] = f[j] + sum;
					newA[i] = a[i];
				}
			}
	}

	cout << f[0] << endl;
}

longest increasing sequence. By dp in quadratic time

This can be solved in )(n) using DP and additional memory.
sum[0] = a[0];
numElements[0] = 1;
OPT[0] = 0;
for ( i = 1; i < n ; i++ ) {
if ( a[i] < a[i-1]) {
m1 = OPT[i-1] + a[i]; // delete current element;
m2 = sum[i] - numElem[i-1]*a[i]; // This is the amount we need to delete on all previous elements to be in sorted order;
if ( m1 < m2) {
OPT[i] = OPT[i-1] + m1;
numElements[i] = numElements[i-1];
} else {
OPT[i] = m2;
numElements[i] = numElements[i-1] + 1;
}
}

This is a discrete dynamic programming. See my code and comments

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
using namespace std;

void main()
{
    // 4, 3, 5, 6 -> 1
    // 10, 3, 11, 12 -> 3
    // 2, 1, 1, 4, 2, 4, 4, 3 -> 5
    // 3,2,4,1-> 2
    vector<int> a = { 3,2,4,1 };
    vector<int> sorted(a);
    sort(begin(sorted), end(sorted));
    vector<unordered_map<int, int>> dp(a.size() + 1);

    // dicrete dynamic programming
    // f(i, j) denotes the sorted array containing a[0...i] with the max element being j.
    // The possible values of j are the discrete set of a[i].
    for(int j = 0; j < a.size(); ++j) {
        for(size_t i = 1; i <= a.size(); ++i) {            
            // When a[i] >= j, f(i, j) = f(i - 1, j) + a[i] - j; decrement a[i] by a[i] - j. Decrementation must have a 
            // less cost than removing a[i]
            if(a[i - 1] >= sorted[j]) dp[i][sorted[j]] = dp[i - 1][sorted[j]] + a[i - 1] - sorted[j];
            // When a[i] < j, f(i, j) = min((f(i - 1, a[i]), f(i - 1, j) + a[i])); do not remove a[i] or remove a[i]
            else dp[i][sorted[j]] = min(dp[i - 1][a[i - 1]], dp[i - 1][sorted[j]] + a[i - 1]);
        }
    }
    cout << dp.back()[sorted.back()] << endl;
}

I will go with the following strategy O(n).

1.Start from the last of the array (traverse array in reverse direction)and put the last element in stack.
2.For all element a[i],
  2.1 Till stack is not empty or stack.top is greater than a[i], keep popping from stack.
  2.2 Now if stack is empty, then simply push a[i] (No element smaller then a[i] to its right) 
  2.3 Otherwise
	2.3.1 If (a[i]-stack.top)>
		F*** ,I am lost, either this is way difficult then I thought it to be or I am fu****g dumb.