Задача с зарубежных стажировок.
Дается массив целых чисел a. Найдите максимальную сумму на подотрезке массива a.
Например: 2 -3 1 1 -1 2
Ответ: 3

Решение:
Люди которых я собеседовал начинают думать сначала в сторону бинарный поиск, два указателя.

Давайте обсудим бинарный поиск.
Если вы решили решать задачу бинарным поиском вы должны задаться вопросом, а где монотонность. Не надо вслепую верить в какую-то идею во время собеседования, так как вам предстоит объяснять и доказывать свое решение.
Что касается монотонности - рассмотрим отрезок [l, r] и отрезок [l, r- 1] видите ли монотонность суммы (увеличивается/уменьшается сумма) ?
Ответ НЕТ, таким образом бинарить нельзя.

Два указателя:
Чтобы решать задачу двумя указателями вы должны ответить себе на вопрос, если я буду сдвигать один из указателей не сделаю ли я хуже ?
Например перебираете указатель r в цикле и сдвигаем указатель l к себе..... Такая себе идея, но часто слышал во время собесов.

А теперь обсудим правильное решение. Вы должны отталкиваться от железно правильного решения, а именно перебрать все отрезки [l, r] и посчитать сумму в этом подотрезке. Работает за O(n^2).
Оптимизируем до линии.
Давайте сначала попытаемся найти максимальную сумму на каком то префиксе. А именно рассмотрим все [0, i] по возрастанию i. Пусть на этом префиксе сумма равна sum. В какой момент вы можете гарантированно сказать, что нам незачем рассматривать префиксы большей длины ?
Очевидно если sum < 0 нам незачем рассматривать префикс [0, i + 1] лучше бы начала рассматривать все отрезки, которые начинаются с позиции i + 1, а именно все отрезки [i + 1, j].
А такую задачу мы решать уже умеем, например удалить префикс длины i и запустить решение выше.
Ответом будет max(sum).
Время работы O(N)
Псевдокод в комментариях.