Задача с собеседования Яндекс

Задача с собеседования Яндекс Задача Дана последовательность a и последовательность a'. Вам требуется найти такие l, r, что отсортировав подмассив a[l:r+1], можно получить массив a'. Если ответов несколько, выберите отрезок наибольшей длины. По условию такая операция всегда существует. Чат алгоритмистов Решение Найдем первое отличающееся вхождение, позицию i: a[i]!= a'[i](то есть самое левое) и найдем последнее (самое правое). Далее расширим эти границы: до тех пор, пока левее от левой границы в приведенном массиве a стоит меньше или равный a'[l-1]<= a'[l], будем двигать его влево. Аналогично и с правым указателем, расширим его вправо. Код l,r=-1,-1 for i in range(n): if a[i]!=aa[i]: r=i if l==-1: l=i while l>0 and aa[l-1]<=aa[l]: l-=1 while r<n-1 and aa[r+1]>=aa[r]: r+=1 print(l+1,r+1) @algoses