DP решение, чтобы найти максимальную длину смежного подмассива с равным числом 0 и 1

Question

Вопрос отсюда https://leetcode.com/problems/contiguous-array/

На самом деле, я нашел решение DP для этого вопроса.Тем не менее, он не пройдет ни одного теста.

Любая мысль?

DP [i] [j] == 1 Значение от подстроки [i] до подстроки [j] допустимо

Разделите вопрос на меньшие

DP [i] [j] == 1

- if DP[i+2][j]==1 and DP[i][i+1]==1
- else if DP[i][j-2]==1 and DP[j-1][j]==1
- else if num[i],num[j] == set([0,1]) and DP[i+1][j-1]==1

`` `current_max_len = 0, если не числа: вернуть current_max_len

    dp = [] * len(nums)
    for _ in range(len(nums)):
        dp.append([None] * len(nums))

    for thisLen in range(2, len(nums)+1, 2):
        for i in range(len(nums)):
            last_index = i + thisLen -1
            if i + thisLen > len(nums):
                continue

            if thisLen==2:
                if set(nums[i:i+2]) == set([0, 1]):
                    dp[i][last_index] = 1
            elif dp[i][last_index-2] and dp[last_index-1][last_index]:
                dp[i][last_index] = 1
            elif dp[i][i + 1] and dp[i + 2][last_index]:
                dp[i][last_index] = 1
            elif dp[i + 1][last_index-1] and set([nums[i], nums[last_index]]) == set([0, 1]):
                dp[i][last_index] = 1
            else:
                dp[i][last_index] = 0
            if dp[i][last_index] == 1:
                current_max_len = max(current_max_len, thisLen)

    return current_max_len

`` `

Answer 1

вот код питона

def func( nums):       
    track,has=0,{0:-1}
    length=len(nums);
    ress_max=0;

    for i in range(0,length):
        track += (1 if nums[i]==1 else -1)
        if  track not in has:
            has[track]=i
        elif ress_max <i-has[track]:
            ress_max = i-has[track]
    return ress_max

l = list(map(int,input().strip().split()))
print(func(l))

Answer 2

Поскольку заданная длина двоичной строки может быть не более 50000.Таким образом, выполнение алгоритма O(n * n) может привести к time limit exceed.Я хотел бы предложить вам решить это в O(n) сложности времени и пространства.Идея такова:

• Если мы возьмем любую действительную непрерывную подпоследовательность и выполним суммирование чисел, считая 0 как -1, то суммарное суммирование должно быть всегда zero.
• Если мы отслеживаем суммирование префикса, то мы можем получить нулевое суммирование в диапазоне от L до R, если суммирование префикса до L - 1 и суммирование префикса до R равны.
• Поскольку мы ищем максимальную длину, мы всегда будем рассматривать индекс вновь найденного суммирования как первый и помещать его в hash map со значением в качестве текущего индекса, который будет сохраняться вечно для этого конкретного суммирования.
• Каждый раз, когда мы вычисляем кумулятивное суммирование, мы смотрим, имеет ли оно какое-либо предыдущее вхождениеЕсли он имеет предыдущее вхождение, мы вычисляем длину и пытаемся максимизировать, иначе она будет первой и будет сохраняться вечно в хэш-карте со значением в качестве текущего индекса.
• Примечание. Чтобы вычислить чистый префикс, мы должны обработать суммирование0 уже на карте и в сочетании со значением -1 в качестве индекса.

Пример кода в C++ выглядит следующим образом:

int findMaxLength(vector<int>& nums) {
    unordered_map<int,int>lastIndex;
    lastIndex[0] = -1;
    int cumulativeSum = 0;
    int maxLen = 0;
    for (int i = 0; i < nums.size(); ++i) {
        cumulativeSum += (nums[i] == 0 ? -1 : 1);
        if (lastIndex.find(cumulativeSum) != lastIndex.end()) {
            maxLen = max(maxLen, i - lastIndex[cumulativeSum]);
        } else {
            lastIndex[cumulativeSum] = i;
        }
    }
    return maxLen;
}

Answer 3

Вот контрпример [1, 1, 0, 0, 0, 0, 1, 1].Проблема с вашим решением состоит в том, что для этого требуется, чтобы список состоял из меньших допустимых списков размера n-1 или n-2, в этом примере счетчика это два списка длиной 4 или n-2.- ПРЕДУПРЕЖДЕНИЕ О СПОЙЛЕРЕ - Вы можете решить проблему, используя другую технику dp, в основном для каждого i, j, вы можете найти количество единиц и нулей между ними в постоянное время, чтобы просто сохранить количество единиц с началасписок для каждого индекса я