具体思路看注释

从左往右找最后一个不满足递增序列的位置

从右往左找最后一个不满足递增序列的位置

为什么不找第一个不满足递增序列的位置呢？

156378
从左往右第一个不满足递增位置的为3，但是明显需要排序的第一个位置为5
从右往左第一个不满足递增的位置为6，但是明显需要排序的第一个位置为3

从左往右最后一个不满足递增序列的位置为3
从右往左最后一个不满足递增序列的位置为5
因此最终返回的需要排序的最短子序列长度为3,5对应下标的差值+1

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int n;
    while (cin >> n)
    {
        vector<int> arr(n, 0);
        for (int i = 0; i < n; i++)
        {
            cin >> arr[i];
        }
        //从左到右记录当前最大数字
        //并左往右找最后一个不满足递增序列的下标
        int max = arr[0];
        int flagj = 0;
        for (int j=1; j < n; j++)
        {
            if (arr[j] < max)
            {
                //记录当前不满足的下标值
                flagj=j;
            }
            else
            {
                //更新当前的最大值
                max = arr[j];
            }
        }
        //从右往左找最后一个不满足递增序列的下标
        int min = arr[n - 1];
        int flagi = 0;
        for ( int i = n - 2; i >= 0; i--)
        {
            if (arr[i] > min)
            {
                //记录当前的不满足的下标值
                flagi=i;
            }
            else
            {
                //更新当前的最小值
                min = arr[i];
            }
        }
        if (flagj >= flagi)
        {
            cout << flagj - flagi + 1 << endl;
        }
        else
        {
            cout << 0 << endl;
        }


    }
    return 0;
}