투자 귀재 규식이 III

투자귀재규식이III.py

def sublist_max(profits):
    max_profit_so_far = profits[0] # 반복문에서 현재까지의 부분 문제의 답
    max_check = profits[0] # 가장 끝 요소를 포함하는 구간의 최대 합
    
    # 반복문을 통하여 각 요소까지의 최대 수익을 저장한다
    for i in range(1, len(profits)):
        # 새로운 요소를 포함하는 구간의 최대합을 비교를 통해 정한다
        max_check = max(max_check + profits[i], profits[i])
        
        # 최대 구간 합을 비교를 통해 정한다
        max_profit_so_far = max(max_profit_so_far, max_check)
    
    return max_profit_so_far

# 테스트 코드
print(sublist_max([7, -3, 4, -8]))
print(sublist_max([-2, -3, 4, -1, -2, 1, 5, -3, -1]))

 

해결과정

 

for문을 돌면서 각 요소까지의 max_profit_so_far와 max_check를 효율적으로 구할 수 있는 방법에 대해서 생각해 본다면,

 

max_check_1 = max(sum([-8]), sum([4, -8]), sum([-3, 4, -8]), sum([7, -3, 4, -8]))를 하나하나 계산할 필요 없이, 바로 전 부분 문제에서 계산한 max_check_2 = max(sum([4]), sum([-3, 4]), sum([7, -3, 4]))을 구했을 때의 값을 저장해 놓으면, 아래 코드로 구할 수 있다.

max_check_1 = max(max_check_2 - 8, -8)

시간복잡도는 O(n) 이 된다.

 

Brute Force방법, Divide and Conquer 방법을 사용할때보다 훨씬 더 시간 복잡도가 단순해졌다.