CC150 17.6

17_6.cpp

/* CC150 17.6 */
// find the smallest sequence m through n s.t. by sorting this sequence the entire array would be sorted

#include <iostream>
#include <vector>

using namespace std;

pair<int, int> findSeq(vector<int> arr)
{
	if (arr.empty()) // empty array
		return make_pair(-1, -1);
	int n = arr.size();
	int left, right;
	for (left = 0; left != n - 1; ++left) { // find the longest leading sorted sequence [0, left]
		if (arr[left] > arr[left + 1])
			break;
	}
	if (left == n - 1) // the whole array is already sorted
		return make_pair(-1, -1);
	for (right = n - 1; right != 0; --right) { // find the longest tailing sorted sequence [right, n-1]
		if (arr[right] < arr[right - 1])
			break;
	}
	int min = arr[right], max = arr[left];
	for (int i = left + 1; i != right; ++i) {
		if (arr[i] < min) min = arr[i]; // minimum of middle and right parts
		if (arr[i] > max) max = arr[i]; // maximum of middle and left parts
	}
	while (left > 0 && arr[left - 1] > min) // maximum of left <= minimum of the rest
		--left;
	while (right < n - 1 && arr[right + 1] < max) // minimum of right >= maximum of the rest
		++right;
	return make_pair(left, right);
}

int main()
{
	vector<int> arr;
	int data;
	while (cin >> data)
		arr.push_back(data);
	pair<int, int> seq = findSeq(arr);
	cout << "(" << seq.first << ", " << seq.second << ")" << endl;
	return 0;
}