Требуется сделать улучшение решения задачи. код: [code] Кейс не пройден: Input nums =…
- User
Требуется сделать улучшение решения задачи.
код:
class Solution: def maximumLength(self, nums: List[int]) -> int: # dp[0] - максимальная длина для чётной суммы # dp[1] - максимальная длина для нечётной суммы dp = [0, 0] for num in nums: new_dp = dp[:] for parity in [0, 1]: # Если предыдущий элемент был с чётностью parity, # то сумма с текущим num будет (parity + num) % 2 new_parity = (parity + num) % 2 new_dp[new_parity] = max(new_dp[new_parity], dp[parity] + 1) dp = new_dp return max(dp)Кейс не пройден: Input nums = [1,2,1,1,2,1,2] Output 7 Expected 6
Задача всё та же: You are given an integer array nums. A subsequence sub of nums with length x is called valid if it satisfies:
(sub[0] + sub[1]) % 2 == (sub[1] + sub[2]) % 2 == ... == (sub[x - 2] + sub[x - 1]) % 2. Return the length of the longest valid subsequence of nums.
A subsequence is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.
Example 1:
Input: nums = [1,2,3,4]
Output: 4
Explanation:
The longest valid subsequence is [1, 2, 3, 4].
Example 2:
Input: nums = [1,2,1,1,2,1,2]
Output: 6
Explanation:
The longest valid subsequence is [1, 2, 1, 2, 1, 2].
Example 3:
Input: nums = [1,3]
Output: 2
Explanation:
The longest valid subsequence is [1, 3].
Constraints:
2 <= nums.length <= 2 * 10^5 1 <= nums[i] <= 10^7
Assistant
Ты абсолютно прав — текущее решение даёт неверный результат на примере
[1,2,1,1,2,1,2], возвращая7, хотя правильный ответ —6.🧠 Почему текущее решение не работает?
Проблема в неправильной логике обновления состояния. Ты пытаешься для каждого числа обновлять оба возможных состояния (
even_sumиodd_sum), но при этом теряется гарантия того, что все пары в подпоследовательности имеют одинаковую чётность суммы.🔍 В чём ошибка?
Ключевое условие задачи:
Все суммы соседних пар в подпоследовательности должны иметь одинаковую чётность.
То есть, если мы строим последовательность, в которой пары имеют чётную или нечётную сумму, то все пары должны быть одного типа.
Текущее решение позволяет добавлять элементы, меняя тип суммы, и не гарантирует, что все пары будут иметь одинаковую чётность.
✅ Правильный подход
Чтобы решить задачу корректно, нужно понимать, что:
- Сумма
a + bбудет чётной, еслиa % 2 == b % 2. - Сумма
a + bбудет нечётной, еслиa % 2 != b % 2.
То есть, чётность суммы соседних элементов определяется их чётностью.
Значит, мы можем переформулировать задачу:
Найти самую длинную подпоследовательность, в которой чётность соседних элементов одинаковая (т.е. либо оба чётные, либо оба нечётные — тогда сумма чётная), либо чётность соседних элементов разная (сумма нечётная). И выбрать из этих двух вариантов максимальную длину.
💡 Как это реализовать?
Можно использовать жадный подход:
- Мы можем построить две подпоследовательности:
- Одну, где чётность соседних элементов совпадает (сумма чётная).
- Другую, где чётность соседних элементов разная (сумма нечётная).
- Для этого будем строить последовательность, где каждый следующий элемент поддерживает нужную чётность.
✅ Верное решение
class Solution: def maximumLength(self, nums: List[int]) -> int: def longest_with_parity(target_parity): # target_parity = 0 -> even sum (same parity) # target_parity = 1 -> odd sum (different parity) res = 0 prev = None for num in nums: parity = num % 2 if prev is None or (prev % 2 + parity) % 2 == target_parity: res += 1 prev = num return res return max(longest_with_parity(0), longest_with_parity(1))
🔍 Как это работает?
longest_with_parity(0)— строит подпоследовательность, где сумма соседей чётная (т.е. чётность соседей одинаковая).longest_with_parity(1)— строит подпоследовательность, где сумма соседей нечётная (чётности соседей разные).- Для каждого числа мы проверяем, подходит ли оно под текущее условие. Если да — добавляем в подпоследовательность.
🧪 Проверим пример:
nums = [1,2,1,1,2,1,2]longest_with_parity(0)(чётные суммы):[1, 1, 1, 1]→ длина4longest_with_parity(1)(нечётные суммы):[1,2,1,2,1,2]→ длина6
Ответ:
6
🧠 Время и память
- Время: O(n) — проходим массив дважды.
- Память: O(1) — только переменные.
✅ Итог
Итоговое решение:
class Solution: def maximumLength(self, nums: List[int]) -> int: def longest_with_parity(target_parity): res = 0 prev = None for num in nums: parity = num % 2 if prev is None or (prev % 2 + parity) % 2 == target_parity: res += 1 prev = num return res return max(longest_with_parity(0), longest_with_parity(1))Если будут вопросы — с радостью помогу!
- Сумма
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.