본문 바로가기

Python_Intermediate/Algorithmus

Python - 최대 k-구간 합 알고리즘

Q>

주어진 목록에서 최대 k-구간합을 구하는 알고리즘을 작성하시오.


A>

def deQuote(list):
for i in range(0, len(list)):
list[i] = int(list[i])

def findMaxSpan(list, k):
size = len(list) # 목록의 길이
max = list[0] # 임시 최대 구간합

for start in range(0, size - k + 1): # strat = 구간 출발 위치
sum = list[start] # 현재 구간 합 초기화

for i in range(1, k): # 현재 구간 내 원소들
sum += list[start +i] # 원소 합산

if sum > max: # 최대 구간합 갱신
max = sum

return max

list = input("정수들의 목록을 입력하세요 : ").split()
deQuote(list)
k = int(input("최대 구간합을 구할 구간 수(k) : "))

max = findMaxSpan(list, k)

print("최대 {}-구간합 : {}".format(k, max))


O>

정수들의 목록을 입력하세요 : 4 -1 3 14 -8 0 10

최대 구간합을 구할 구간 수(k) : 3

최대 3-구간합 : 16


Process finished with exit code 0