

#最大子段和最短子序列

def max_sequence(arr):
    ans = arr[0]
    cur = 0
    for i in arr:
        cur += i
        if cur > ans:
            ans = cur
        if cur < 0:
            cur = 0
    return ans

'''
# O(n^2)
def min_sequence_morethan_s(arr, s):
    n = len(arr)+1
    prefix_sum = [0]*n # for more simple, prefix_sum save in [1:n]
    for i in range(1,n):
        prefix_sum[i] = prefix_sum[i-1]+arr[i-1]
    ans = n
    for i in range(1,n):
        for j in range(i,n):
            if prefix_sum[j]-prefix_sum[i-1] >= s:
                ans = min(ans, j-i+1)
    return ans  # there is not answer if ans == len(arr)+1
'''

# O(n)
def min_sequence_morethan_s(arr, s):
    n = len(arr)+1
    prefix_sum = [0]*n # for more simple, prefix_sum save in [1:len(arr)+1]
    for i in range(1,n):
        prefix_sum[i] = prefix_sum[i-1]+arr[i-1]
    i, ans = 1, n+1
    for j in range(1,n):
        if prefix_sum[i-1] > prefix_sum[j]-s:
            continue
        while prefix_sum[i] <= prefix_sum[j]-s:
            i += 1
        ans = min(ans,j-i+1)
    return ans # there is not answer if ans == len(arr)+1





if __name__ == '__main__':
    pass
