글 읽기 - 시간초과(1912번)

chanugod 7년 전 0

시간초과를해결할 방버이 있나요??

def main():
    x=eval(input(''))
    y=input('')
    lst=[]
    t=0
    for i in range(x):
        t+=eval(y.split(' ')[i])
        lst.append(t)
    t=maxdiff(lst)
    print(t)


def maxdiff(lst):
    if(len(lst)==1):
        return lst[0]
    if(len(lst)==2):
        return max(lst[0], lst[1], lst[1]-lst[0])
    m=(len(lst)-1)//2
    x1=maxdiff(lst[:m+1])
    x2=maxdiff(lst[m+1:])
    min1=lst[0]
    max1=lst[m+1]
    for i in range(m+1):
        if(min1>lst[i]):
            min1=lst[i]
    for j in range(m+1,len(lst)):
        if(max1<lst[i]):
            max1=lst[i]
    x3=max1-min1
    return max(x3,x2,x1)


main()

chanugod 7년 전 0

제 생각이 이 시간복잡도는 length ln(length)인거 같은데 이거보다 더 좋은 방법이 있나요?

baekjoon 7년 전 1

이 방법은 length^2 ln(length) 입니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

시간초과(1912번)

chanugod 7년 전 0

chanugod 7년 전 0

baekjoon 7년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말