python - 最多有 K 个元素的最大连续子数组

Question

有没有办法在 O(N) 复杂度中找到最多 K 个元素的最大连续子数组。

或者不存在这种可能性。

例如：

A = [4, -2, 6, 4, -2, 6]

K = 3

因为中间的 6 和 4 等于 10，所以函数应该返回 10。

PS 与 O(N K) 很容易，问题是在 O(N) 中是否可能这是一个在 O(N K) 时间内解决的算法：

def maxContiguousFragment(arr):
    b = max(arr)
    s = 0
    for i in arr:
        s = max(s + i, i)
        b = max(s, b)
    return b

def max_K_Subarray(arr,k):
    return max(maxContiguousFragment(
            arr[i:i+k] for i in range(len(arr)-k)))

标签： pythontime-complexitymaxsub-arraycontiguous