백준 2559 : 수열 with 파이썬

https://www.acmicpc.net/problem/2559

2559번: 수열

 

1. sum()을 이용하면 시간복잡도가 O(n)이 되므로 시간초과

n,k=map(int, input().split())
num=list(map(int, input().split()))

maxv=0
for i in range(n):
    tmp=sum(num[i:i+k])   #sum()의 시간복잡도는 O(n)
    maxv=max(maxv, tmp)   #max()의 시간복잡도는 O(n)
    
print(maxv)

 

2. 따라서 투포인터를 이용해 앞의 인덱스를 빼주고, 뒤의 인덱스를 더해주며 each값을 갱신하기

n,k=map(int, input().split())
nums=list(map(int, input().split()))

each=sum(nums[:k])
maxv=each    
for i in range(k,n):
    each+=nums[i]
    each-=nums[i-k]
    maxv=max(maxv, each)
print(maxv)