smallest cut of an array to make it sorted

[husseinmd]

hey ..
i need help
i am supposed to make a program that take a list of integers from the user and to delete the smallest part of it in order to make it sorted in non decreasing order ..
example : input : 1 2 3 4 5 8 7 6 7 8 9
output : 1 2 3 4 5 6 7 8 9 ( delete : 8 7 )
i need a code that use a technique similar to the merge function to achieve linear time ..
please help me !
this code works but it is in quadratic time :


int main ()
{
cout<<"Enter a list of numnbers ending with the sentinel -999:"<<endl;
int A[1000];
int n = 0;
int x;
cin>>x;
while(x!=-999)
{
A[n] = x;
n++;
cin>>x;
}

// check if sorted

bool sorted = true;
int i;
for(i=0;i<n-1;i++)
if(A[i+1]<A[i])
{
sorted = false;
break;
}
if(sorted)
{
cout<<"Array sorted: no cut needed"<<endl;
return 0;
}

int i0 = i; // i0 = largest i such that A[0...i0] is sorted
// now find j0 = smallest j such that A[j...n-1] is sorted
int j0;
for(j0=n-1;j0>0;j0--)
if(A[j0-1]>A[j0])
break;

int icut, jcut;

// we are looking for the smallest array A[icut ... jcut] whose removal makes A sorted


// try the cut A[0 ... j0-1] (length = j0) and the cut A[i0+1...n-1] (length = n-1-(i0+1)+1 = n-i0-1 )
// and take the smallest

if(j0<n-i0-1)
{
icut = 0;
jcut = j0-1;
}
else
{
icut = i0+1;
jcut = n-1;
}


// now check if there is a smaller cut
// any cut is of the form A[i...j] for some 1=<i<=i0+1 and j0-1<=j<=n- 2 such that A[i-1]<=A[j+1]
// we are looking for smallest one (length = j-i+1)

for(i=1;i<=i0+1;i++)
for(int j=j0-1;j<=n-2;j++)
if(j-i+1<jcut - icut+1 && A[i-1]<=A[j+1])
{
icut = i;
jcut = j;
}


cout<<"Min cut length ="<<jcut-icut+1<<". It starts at index "<<icut<<"and ends at index "<<jcut<<endl;
cout<<"(remove the elements:";
for(i=icut;i<=jcut;i++)
cout<<A[i]<<" ";
cout<<")."<<endl;

}

return 0;

}

[zoran404]

I didn't looked at your code, but this is my idea:
Get 2 ints (you'll need 2 ints first and seconds, those will be indexes of the array elements) and check if the second one is smaller than the first.
If it is not then set first to secong and second to next element of the array.
Else change the value of the first one to -2^31 (the bigggest negative value int can hold) and set first to second and second to next array element.
That should do the job.

Edit: Forgot to the second part, when you go trught the whole array you have to go trugh it again and you will still need first and second int variables.
At start first will be first element and second will be second. After each loop you will increment first and second (like in the previus for loop).
If element at index first is equal to -2^31 then check if second is equal to -2^31 increment second (so he would be the index of the next element) and check again. If second is not -2^31 assign second to first. Do this till you reach the end of the array.

Hope you understanded this and that I didn't miss to mention anything.

[husseinmd]

yes i understood it , however i think it won't work ,
let's take this example : 1 2 3 4 8 7 2 3 4 5
using ur code , this will be 1 2 3 4 2 3 4 5 , which it is not sorted ,
and i didn't notice when u used a technic similar to the murge function :( that was the question ..
anw thx alot and hope u could help me again :)

[JLBorges]

> i need a code that use a technique similar to the merge function to achieve linear time ..

See: http://en.wikipedia.org/wiki/Patience_sorting#Algorithm_for_finding_a_longest_increasing_subsequence

[zoran404]

Huh, you are right, if I would increment only second when it is false it would sort the array, but I think I should have some more if statements in deleting part to check is it better to delete left or right array element(s)