題目:給定一個(gè)無(wú)序數(shù)組arr, 其中元素可正卓练、可負(fù)隘蝎、可0。給定一個(gè)整數(shù)k昆庇，求arr所有子數(shù)組中累加和為k的最長(zhǎng)子數(shù)組長(zhǎng)度末贾。
分析：先采用快速排序算法對(duì)數(shù)組進(jìn)行排序，再進(jìn)行判斷每個(gè)子數(shù)組的長(zhǎng)度整吆，取最長(zhǎng)得長(zhǎng)度拱撵。
code：
#[n,k] = list(map(int,input().split()))
#inp = list(map(int,input().split()))
def quick_sort(lists, left, right):
? ? if left > right:
? ? ? ? return lists
? ? key = lists[left]
? ? low = left
? ? high = right
? ? while left < right:
? ? ? ? if left < right and lists[right] >= key:
? ? ? ? ? ? right -= 1
? ? ? ? lists[left] = lists[right]
? ? ? ? if left < right and lists[left] <= key:
? ? ? ? ? ? left += 1
? ? ? ? lists[right] = lists[left]
? ? lists[right] = key
? ? quick_sort(lists, low, left - 1)
? ? quick_sort(lists, left + 1, high)
? ? return lists
[n, k] = 5, 3
inp =? [1, -2, 1, 1, 1]#[1, 2, 1, 1, 1]
inp = quick_sort(inp, 0, len(inp) - 1)
maxLen = 0
Sum = 0
l = 0
for i in range(len(inp)):
? ? Sum += inp[i]
? ? if Sum > k:
? ? ? ? Sum -= inp[l]
? ? ? ? l += 1
? ? if i - l + 1 > maxLen:
? ? ? ? maxLen = i - l + 1
print(maxLen)
程序運(yùn)行結(jié)果為：
5
