Sub Sort

16.16 Sub Sort: Given an array of integers, write a method to find indices m and n such that if you sorted elements m through n, the entire array would be sorted. Minimize n - m (that is, find the smallest such sequence).

EXAMPLE
Input: 1, 2, 4, 7, 10, 11, 7, 12, 6, 7, 16, 18, 19
Output: (3, 9)

• Iterate from the beginning, and make sure every element after it is large than it. When it is not, return this index. Now iterating from the end, and make sur every element before it is smaller than it. When it is not, return that index.

pair<int, int> sub_sort(vector<int> &nums) {
    // assume to be sorted, and then change values if needed
    pair<int, int> n_m = { make_pair(0, nums.size() - 1) };
    if (nums.size() < 2) {
        cout << "Is sorted" << endl;
        return n_m;
    }

    bool notstop = true;
    for (int i = 0; i < nums.size() && notstop; i++) {
        for (int j = i+1; j < nums.size() && notstop; j++) {
            //cout << nums.at(i) << "<" << nums.at(j) << endl;
            if (nums.at(i) >= nums.at(j)) {
                n_m.first = i;
                notstop = false;
            }
        }
    }

    notstop = true;
    for (int i = nums.size() - 1; i >=0 && notstop; i--) {
        for (int j = i - 1; j >= 0 && notstop; j--) {
            //cout << nums.at(i) << "<" << nums.at(j) << endl;
            if (nums.at(i) <= nums.at(j)) {
                n_m.second = i;
                notstop = false;
            }
        }
    }

    return n_m;
}

int main()
{
    vector<int> nums = { 1, 2, 4, 7, 10, 11, 7, 12, 6, 7, 16, 18, 19 };
    cout << sub_sort(nums).first << " ";
    cout << sub_sort(nums).second << endl;

    nums = { 1,2,3,4,5 };
    cout << sub_sort(nums).first << " ";
    cout << sub_sort(nums).second << endl;
}