python 최대구간


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) 이러면 되는거 아닌가요?>

라고 누가 설명해주시기는 했는데 더 이해가 안가요 ㅠㅠ

명쾌한 답 부탁드립니다.,

  • 2016년 05월 15일에 작성됨
    학생.직장인

  • 최대 구간이 뭔가요?    정두식   2016.5.15 11:55     
조회수 390


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 > maxTrue일 경우 max가 바뀌고, 이 때 인덱스 i을 변경해 주면됩니다.

for문 하나로 리스트에 값과 인덱스를 조회하는 방법은 다음과 같습니다.

for idx, value in enumerate(list):
  • 2016년 05월 15일에 작성됨
    시원한 날만 일하자

로그인이 필요한 기능입니다.

Hashcode는 개발자들을 위한 무료 QnA사이트 입니다. 작성한 답변에 다른 개발자들이 댓글을 작성하거나 좋아요/싫어요를 할 수 있기 때문에 계정을 필요로 합니다.
► 로그인
► 계정만들기
Close