k 停留在标志逻辑的不同子数组的最大和

Question

问题

您已经给出了一个整数数组 nums 和整数 k。求满足以下条件的所有 nums 子数组的最大子数组和。

问题链接

思维过程

保留一个标记以知道何时确定要进行比较。当使用字典有多个频率时，将标志更新为 false。问题是，如果存在多个差异，那么我不知道何时将标志恢复为 true？我对此有点迷失。任何想法都会对我有帮助。具体来说，我无法通过测试中的第三种情况。

代码

class Solution:
    def maximumSubarraySum(self, a, k):
        sumSoFar, toReturn, i, j = 0, 0, 0, 0
        canIcount = True
        eleToFreq = dict()
        N = len(a)

        if len(set(a)) < k:  # Handle all-duplicate case
            return 0

        while j < N:
            if j >= k - 1:
                if a[j] in eleToFreq:
                    eleToFreq[a[j]] += 1
                    canIcount = False
                else:
                    eleToFreq[a[j]] = 1
                sumSoFar += a[j]
                if canIcount:
                    toReturn = max(toReturn, sumSoFar)
                #print('does ' , eleToFreq, ' have ', a[i])
                if eleToFreq[a[i]] >= 1:
                    eleToFreq[a[i]] -= 1
                else:
                    eleToFreq.pop(a[i])
                sumSoFar-=a[i]
                i+=1
                j+=1
            else:
                if a[j] in eleToFreq:
                    eleToFreq[a[j]] += 1
                    canIcount = False
                else:
                    eleToFreq[a[j]] = 1
                sumSoFar += a[j]
                j+=1

        return toReturn


solution = Solution()
arr = [1, 5, 4, 2, 9, 9, 9]
k = 3
a = solution.maximumSubarraySum(arr, k)
print("Output:", a)
# Expected output: 15 actual output: 15

arr = [4, 4, 4]
k = 3
a = solution.maximumSubarraySum(arr, k)
print("Output:", a)
# Expected output: 0 actual output: 0

arr = [1,1,1,7,8,9]
k = 3
a = solution.maximumSubarraySum(arr, k)
print("Output:", a)
# Expected output: 24 actual output:0

Answer 1

这是一个有效的解决方案。由于嵌套结构（即许多 if-else 语句），您的代码很难阅读。这使得调试变得困难。

我建议从问题中创建小任务（例如函数），例如(1) 从数组中创建 k 个元素的子数组，(2) 创建总和，(3) 检查它们是否不同，以及 (4) 定义不同子数组的最大和。

在我的解决方案中，我通过对子数组使用数据类对象来提高可读性（一步解决 1-3），然后在新函数中评估子数组列表。

from dataclasses import dataclass


@dataclass
class Subarray:
    arrays: list
    sums: int
    distinct: bool

class Solution:

    def __init__(self, length: int, array: list) -> None:
        self._length = length
        self._array = array

        self._subarrays = []

    def maximum_subarray_sum(self):
        start = 0
        end = start + self._length

        while end <= len(self._array):
            sub_array = self.create_subarray(start, end)
            self._subarrays.append(sub_array)
            start += 1
            end += 1

        return self.eval_subarrays()

    def eval_subarrays(self):
        possible_output = [sub_array.sums for sub_array in self._subarrays if sub_array.distinct is True]
        if len(possible_output) == 0:
            return 0
        return max(possible_output)

    def create_subarray(self, start: int, end: int):
        entries = self._array[start: end]
        is_disinct = (len(set(entries)) == len(entries))
        sub_array = Subarray(entries, sum(entries), is_disinct)
        return sub_array

arr = [1, 5, 4, 2, 9, 9, 9]
k = 3
solution = Solution(k, arr)
a = solution.maximum_subarray_sum()
print("Output:", a)
# Expected output: 15 actual output: 15

arr = [4, 4, 4]
k = 3
solution = Solution(k, arr)
a = solution.maximum_subarray_sum()
print("Output:", a)
# Expected output: 0 actual output: 0

arr = [1,1,1,7,8,9]
k = 3
solution = Solution(k, arr)
a = solution.maximum_subarray_sum()
print("Output:", a)
# Expected output: 24 actual output:24

Answer 2

问题是，如果存在多个差异，那么我不知道何时将标志转回 true？

这就是为什么单个标志

canIcount 

是不够的。您需要记录“有多少次”违反唯一约束的情况。因此，请使用名为 canIcount

 的计数器变量来代替 

numDuplicates另一个问题是条件

eleToFreq[a[i]] >= 1

，它应该是

eleToFreq[a[i]] > 1

，就像在其他情况下您想要弹出条目一样。通过对代码进行最小更改来适应这两件事，我们得到了这个工作代码（注意使用

numDuplicates

的位置）：

class Solution:
    def maximumSubarraySum(self, a, k):
        sumSoFar, toReturn, i, j = 0, 0, 0, 0
        numDuplicates = 0
        eleToFreq = dict()
        N = len(a)

        if len(set(a)) < k:
            return 0

        while j < N:
            if j >= k - 1:
                if a[j] in eleToFreq:
                    eleToFreq[a[j]] += 1
                    numDuplicates += 1
                else:
                    eleToFreq[a[j]] = 1
                sumSoFar += a[j]
                if numDuplicates == 0:
                    toReturn = max(toReturn, sumSoFar)
                
                if eleToFreq[a[i]] > 1:  # correction of condition
                    eleToFreq[a[i]] -= 1
                    numDuplicates -= 1
                else:
                    eleToFreq.pop(a[i])
                sumSoFar -= a[i]
                i+=1
                j+=1
            else:
                if a[j] in eleToFreq:
                    eleToFreq[a[j]] += 1
                    numDuplicates += 1
                else:
                    eleToFreq[a[j]] = 1
                sumSoFar += a[j]
                j+=1

        return toReturn