Блог

Проблема: вам нужно найти самый длинный подмассив с нечетной суммой в заданном массиве целых чисел, но как временная сложность, так и вспомогательное пространство должны быть лучшими.

Я пытался обойти массив с помощью цикла while и двух переменных для индексов (low, high while (low <= high) …), но я не каждый раз получал хорошие ответы…

Я пробовал это: (сумма — это общая сумма массива)

 while (low <= high) {

            if((sum - a[low]) % 2 != 0)
                return (high - low);

            else if((sum - a[high]) % 2 != 0)
                return (high - low);

            else{
                if((sum - a[low]) % 2 == 0){
                    sum -= a[low];
                    low  ;
                }

                if((sum - a[high]) % 2 == 0){
                    sum -= a[high];
                    high--;
                }
            }
        }
  

Для {2, 2, 2, 1, 1, 2, 2, 2, 2} я бы ожидал вывода 5
но я получаю 2

1. Если весь массив нечетный, то вы его получили.
2. Если он четный, вам нужно найти четное число, ближайшее к концу массива.
   • Если это число близко к началу, то результатом является подмассив от следующей позиции до конца
   • если это число близко к концу, то результатом является подмассив от начала до этого числа (исключая само число).