面试题:给定一个数组和一个整数k,找出每个大小为k的连续子数组的最大值。
Sample Input :
1 2 3 1 4 5 2 3 6
3 [ value of k ]
Sample Output :
3
3
4
5
5
5
6
我想不出比暴力更好的方法了。最坏情况是当数组按降序排序时,时间复杂度为O(nk)。
面试题:给定一个数组和一个整数k,找出每个大小为k的连续子数组的最大值。
Sample Input :
1 2 3 1 4 5 2 3 6
3 [ value of k ]
Sample Output :
3
3
4
5
5
5
6
我想不出比暴力更好的方法了。最坏情况是当数组按降序排序时,时间复杂度为O(nk)。
O(logk)
。MultiSet
。在Java中,您可以使用TreeMap
(map,因为需要计算每个元素出现的次数,而Java不提供 Multi- 集合)。for (int i = 0; i < n; ++i) {
tree.add(a[i]);
if (tree.size() > k) {
tree.remove(a[i - k]);
}
if (tree.size() == k) {
print(tree.max());
}
}
def MaxContigousSum(lst, n):
m = [0]
if lst[0] > 0:
m[0] = lst[0]
maxsum = m[0]
for i in range(1, n):
if m[i - 1] + lst[i] > 0:
m.append(m[i - 1] + lst[i])
else:
m.append(0)
if m[i] > maxsum:
maxsum = m[i]
return maxsum
lst = [-2, 11, -4, 13, -5, 2, 1, -3, 4, -2, -1, -6, -9]
print MaxContigousSum(lst, len(lst))
**Output**
20 for [11, -4, 13]