17.6 给定一个整数数组，编写一个函数，找出索引m和n，只要将m和n之间的元素排好序，整个数组就是有序的。注意：n越小越好，也就是说，找出符合条件的最短序列。
解法：
开始解题之前，让我们先确认一下答案会是什么样的。如果要找的是两个索引，这表明数组中间有一段有待排序，其中数组开头和末尾部分是排好序的。
现在，我们借用下面的例子来解决此题：
1,2,4,7,10,11,7,12,6,7,16,18,19
首先映入脑海的想法可能是，直接找出位于开头的最长递增子序列，以及位于末尾的最长递增子序列。
左边：1,2,4,7,10,11
中间：7,12
右边：6,7,16,18,19
很容易就能找出这些子序列，只需从数组最左边和最右边开始，向中间查找递增子序列。一旦发现元素大小顺序不对，那就是找到了递增/递减子序列的两头。
但是，为了解决这个问题，还需要对数组中间部分进行排序，只要将中间部分排好序，数组所有元素便是有序的。具体来说，就是一下判断条件必须为真：
//左边所有元素都要小于中间所有元素
min(middle)>end(left)
//中间所有元素都要小于右边的所有元素
max(middle)<start(right)
或者，换句话说，对于所有元素：
left<middle<right
实际上，上例的这个条件绝对不可能成立。根据定义，中间部分的元素是无序的。而在上面的例子中，left.end>middle.start且middle.end>right.start一定成立。这样一来，只排序中间部分并不能让整个数组有序。
不过，我们还可以缩减左边和右边的子序列，直到先前的条件成立为止。
令min等于min(middle)，max等于max(middle).
对左边部分，我们先从这个子序列的末尾开始，并向左移动，直到找到元素索引i使得array[i]<min;找到后只需排序中间部分，就能让数组的那部分有序。
然后，对右边部分进行类似操作。
C++实现代码：
#include<iostream>
using namespace std; int findEndOfLeftSubsequence(int array[],int n)
{
int i;
for(i=;i<n;i++)
{
if(array[i]<array[i-])
return i-;
}
return n-;
} int findEndOfRightSubsequence(int array[],int n)
{
int i;
for(i=n-;i>=;i--)
{
if(array[i]>array[i+])
return i+;
}
return ;
} int shrinkLeft(int array[],int n,int min_index,int start)
{
int comp=array[min_index];
cout<<comp<<endl;
int i;
for(i=start-;i>=;i--)
{
if(comp>=array[i])
return i+;
}
return ;
} int shrinkRight(int array[],int n,int max_index,int start)
{
int comp=array[max_index];
cout<<comp<<endl;
for(int i=start;i<n;i++)
{
if(comp<=array[i])
return i-;
}
return n-;
} void findUnsortedSequence(int array[],int n)
{
int end_left=findEndOfLeftSubsequence(array,n);
cout<<end_left<<endl;
int start_right=findEndOfRightSubsequence(array,n);
cout<<start_right<<endl;
int min_index=end_left+;
if(min_index>=n)
return;
int max_index=start_right-;
for(int i=end_left;i<=start_right;i++)
{
if(array[i]<array[min_index])
min_index=i;
if(array[i]>array[max_index])
max_index=i;
}
cout<<array[min_index]<<" "<<array[max_index]<<endl;
int right_index=shrinkRight(array,n,max_index,start_right);
int left_index=shrinkLeft(array,n,min_index,end_left);
cout<<left_index<<" "<<right_index<<endl;
} int main()
{
int arr[]={,,,,,,,,,,,};
findUnsortedSequence(arr,);
}