零子數(shù)組：對(duì)于長(zhǎng)度為N的數(shù)組，求連續(xù)子數(shù)組和和最接近0的值和子數(shù)組
最大連續(xù)子數(shù)組：給定一個(gè)數(shù)組A嫉嘀，求A的連續(xù)子數(shù)組炼邀，使該子數(shù)組和最大
數(shù)字連續(xù)子數(shù)組：給定長(zhǎng)度為N的數(shù)組A，求遞增且數(shù)字連續(xù)最長(zhǎng)子數(shù)組
# 數(shù)字連續(xù)子數(shù)組
def maxcontinue_sequence(arr):
count = [1]*len(arr)
maxT = 1
to = 0
for i in range(1, len(arr)):
if arr[i] - arr[i-1] == 1:
count[i] += count[i-1]
maxT = max(maxT, count[i])
if maxT == count[i]:
to = i
frm = to - maxT + 1
return [frm, to, maxT]
# 最大連續(xù)子數(shù)組
def maxsum_sequence(arr):
seqsum = 0
maxseqsum = 0
frm = to = 0
start = frm
for i in range(len(arr)):
if seqsum <= 0:
seqsum = arr[i]
frm = i
else:
seqsum += arr[i]
maxseqsum = max(maxseqsum, seqsum)
if maxseqsum == seqsum:
to = i
start = frm
return [start, to, maxseqsum]
# 零子數(shù)組
def zerosum_sequence(arr):
sumarr = [0]*len(arr)
sumarr[0] = arr[0]
for i in range(1, len(arr)):
sumarr[i] = sumarr[i-1] + arr[i]
InsertSort(sumarr, 1)
minsub = abs(sumarr[1] - sumarr[0])
minsubidx = 0
for i in range(1, len(arr)):
sub = abs(sumarr[i] - sumarr[i-1])
if sub < minsub:
minsub = sub
minsubidx = i
tmpsum = 0
start = end = -1
for j in range(len(arr)):
tmpsum += arr[j]
if tmpsum in (sumarr[minsubidx], sumarr[minsubidx-1]):
if start == -1:
start = j+1
else:
end = j
break
return [start, end, minsub]
if __name__ == "__main__":
# arr = [1, 2, 3, 4, 7, 9, 10, 13, 17]
# print maxcontinue_sequence(arr)
# arr = [1, -2, 3, 4, -7, 9, 10, -13, -17, -2]
# print maxsum_sequence(arr)
# arr = [1, -2, 3, 10, -4, 7, 2, -5]
arr = [1, -2, 3, 5, -7, 2, 12, -13, -17, -2]
print zerosum_sequence(arr)
