Skip to content
TheChatArchiveThe Chat Archive
Qwenqwen3-235b-a22b-no-thinking· Alibaba (Qwen)Hugging Face LMArena Human Preference 140K

Требуется сделать улучшение решения задачи. код: [code] Кейс не пройден: Input nums =…

From a Chatbot Arena battleThe same person sent this prompt to two anonymous models at once. Compare it with Metallama-3.3-70b-instruct’s answer.
  1. 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

  2. Qwen 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.

    То есть, чётность суммы соседних элементов определяется их чётностью.

    Значит, мы можем переформулировать задачу:

    Найти самую длинную подпоследовательность, в которой чётность соседних элементов одинаковая (т.е. либо оба чётные, либо оба нечётные — тогда сумма чётная), либо чётность соседних элементов разная (сумма нечётная). И выбрать из этих двух вариантов максимальную длину.


    💡 Как это реализовать?

    Можно использовать жадный подход:

    1. Мы можем построить две подпоследовательности:
      • Одну, где чётность соседних элементов совпадает (сумма чётная).
      • Другую, где чётность соседних элементов разная (сумма нечётная).
    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] → длина 4
    • longest_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))
    

    Если будут вопросы — с радостью помогу!

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.