[백준/Python] 수열 2559

알고리즘 분류 : 투포인터, 누적합, 슬라이딩윈도우

시간 복잡도 : O(N-K)

 

Try_1) Fail

• sum 함수를 사용하여 temp_sum을 구현
• sum은 O(N)이라서 TLE 발생

Try_2) Success

• temp_sum을 list indexing으로 접근
• list indexing은 O(1)이라서 통과

"""
Condition
    - TL : 1s (대략 2000만)
    - ML : 128mb (대략 32*10만)
    - 2<=N<=10만, 1<=K<=N, -100<=sequence<=100

Question
    - 주어진 수열에서, 연속적인 K개의 부분수열 합이 최대가 되는 값은?

Access
    - 똑같은 K 길이의 합을 비교해야 하므로, 슬라이딩 윈도우로 접근하자

1. temp_sum = sum(temperature[p1:p2]) 라 하면
    for문 = O(N-K)
    temp_sum = O(K)
    >>> O[(N-K)*K]
    >>> N=70만,K=30만일때 > 40만 * 30만 = TLE 발생

2. temp_sum = temp_sum - temperatur[p1-1] + temperature[p2]라 하면
    for문 = O(N-K)
    temp_sum = O(1)
    >>> O(N-K)
    >>> N=70만,K=30만일때 > 40만 = 통과
"""

from sys import stdin
input=stdin.readline

#input&set data
n,k = map(int,input().split())
temperature = list(map(int,input().split()))

#define function
def solution():
    p1=0
    p2=k-1
    temp_sum = sum(temperature[p1:p2+1])
    max_sum  = temp_sum
    for _ in range(n-k): # O(N-K)
        p1 +=1
        p2 +=1
        temp_sum = temp_sum -temperature[p1-1] + temperature[p2]
        max_sum = max(temp_sum, max_sum)
    return max_sum

#main()
print(solution())