零子数组：对于长度为N的数组，求连续子数组和和最接近0的值和子数组
最大连续子数组：给定一个数组A，求A的连续子数组，使该子数组和最大
数字连续子数组：给定长度为N的数组A，求递增且数字连续最长子数组

# 数字连续子数组
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]

# 最大连续子数组
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]

# 零子数组
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)