[알고리즘 일기] 38. 투자 귀재 규식이3

문제 38. (2021-06-07)

투자 귀재 규식이3

이미 sublist_max 함수를 각각 Brute Force과 Divide and Conquer 방식으로 작성했는데요. Brute Force로 풀었을 때는 시간 복잡도가 O(n2), Divide and Conquer를 사용했을 때는 O(nlgn)였습니다.

이에는 시간 복잡도를 O(n)로 한 번 더 단축해보세요!

❧ 테스트 셋

def sublist_max(profits):
    # Code

# Test
print(sublist_max([7, -3, 4, -8]))
print(sublist_max([-2, -3, 4, -1, -2, 1, 5, -3, -1]))

❧ 출력 예시

8 
7

---

❧ 정답

def sublist_max(profits):
    # max_profit_so_far : 현재 인덱스 이전까지의 최대 수익(부분 문제)
    max_profit_so_far = profits[0]
    '''
    max_check : 현재 인덱스를 포함하여 나올 수 있는 최대 수익
    max 함수를 이용해, 이전 max_check 값과 현재 인덱스 값을 비교
    '''
    max_check = max(profits[0]+profits[1], profits[1])
    for i in range(2, len(profits)):
        max_profit_so_far = max(max_profit_so_far, max_check)
        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]))

1️⃣ 시간 복잡도 : O(logn)

2️⃣ 이전 Divide and Conquer 방법, Brute Force 방법보다 효율적