2021-11-20 투자구간에서 최대수익

1. Brute Force

기본 값으로 가장 첫 날의 수익을 지정

 

수익은 지금까지의 구한 수익 + 당일 수익 으로 구할 수 있다.

 

def sublist_max(profits):
    
    profit = [profits[0]]
    for i in range(1, len(profits)):
        profit.append(profit[i-1] + profits[i])
    return max(profit)

 

2. Divide and Conquer

 

basecase는 start == end

 

수익율이 최대인 구간은 리스트 중앙을 기준으로 왼쪽에 있거나 오른쪽에 있거나 중앙을 관통할 수 있다.

리스트를 좌 우 로 나누는 것은 재귀로 해결

 

중앙을 관통하는 구간의 최대값을 알기 위해서는 따로 함수의 분리 필요 -> 기능이 필요하기 때문에.

 

def max_crossing_sum(profits, start, end):
    mid = (start + end)//2
    leftCount = 0
    leftMax = profits[mid]
    
    for i in range(mid, start-1, -1):
        leftCount += profits[i]
        leftMax = max(leftCount, leftMax)
        
    
    rightCount = 0
    rightMax = profits[mid+1]
    
    for i in range(mid+1, end):
        rightCount += profits[i]
        rightMax = max(rightMax, rightCount)
    
    return rightMax + leftMax
        


def sublist_max(profits, start, end):
    if start == end:
        return profits[start]
    
    mid = (start+end)//2
    
    leftMax = sublist_max(profits, start, mid)
    rightMax = sublist_max(profits, mid+1, end)
    centerMax = max_crossing_sum(profits, start, end)
    
    return(max(leftMax, rightMax, centerMax))

 

3. Greedy 

구간에서 가장 큰 수익을 보려면, 최대한 수익이 난 부분을 선택해야한다. 

구간 내에서 수익이 난 부분을 모두 포함해야 하므로 수익이 있는 인덱스를 선택해준 뒤에

그 사이 구간 합을 더하는게 greedy하게 푸는 법!

 

def sublist_max(profits):
   
    container = []
    for i in range(len(profits)):
        if profits[i] > 0:
            container.append(i) 
    return sum(profits[container[0]:container[-1]+1])

 

2021-11-20