python 최대구간
조회수 2471회
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): sum = list[start]
for i in range(1, k): sum += list[start + i]
if sum > max: max = sum
return max list = raw_input("정수들의 목록을 입력하세요: ").split() deQuote(list) k = input("최대 k-구간합을 구할 구간 수: ")
max = findMaxSpan(list, k)
print "최대", k,"-구간합: ", max
요래 최대구간합은 구했는데 최대 구간을 구하기가 어렵네요.
mavVal = -99999 (int.min?) i = 0 선언해두고 그냥 for j in range len(list) 돌려서 maxVal > 구간합 maxVal = 구간합 i = j
return (i, i + 2) 이러면 되는거 아닌가요?>
라고 누가 설명해주시기는 했는데 더 이해가 안가요 ㅠㅠ
명쾌한 답 부탁드립니다.,
-
(•́ ✖ •̀)
알 수 없는 사용자
1 답변
-
인자
list
에서 길이가 k인 subarray 중 가장 합이 큰걸 찾아내는 코드 아닌가요?def findMaxSpan(list, k): size = len(list) max = list[0] #문제 for start in range(0, size - k + 1): sum = list[start] for i in range(1, k): sum += list[start + i] if sum > max: #답변 max = sum return max
우선 최대구간을 구하는 코드 자체에 문제가 있습니다.
max = list[0]
와 같이 설정하면,list = [3,-1,-3,-2]
같이 리스트에 음수 정수가 있을 경우 원하는 리턴값이 안나옵니다.
질문하신 최대구간으로 넘어오면,
subarray의 길이
k
가 주어져 있으니 최대구간은 [최대합을 가지는 subarray가 시작하는 인덱스i
,i+k-1
] 까지일거고, 그렇다면i
를 알아내는 코드를 추가해줘야합니다.sum > max
가True
일 경우max
가 바뀌고, 이 때 인덱스i
을 변경해 주면됩니다.for문 하나로 리스트에 값과 인덱스를 조회하는 방법은 다음과 같습니다.
for idx, value in enumerate(list):
-
(•́ ✖ •̀)
알 수 없는 사용자
-
댓글 입력