최대 부분 배열 합 (Dynamic Programming)

# 최대 부분 배열 합이란?

개념은 아주 간단합니다. 주어진 수 배열에서 연속된 부분 배열 중 합이 최대인 부분 배열을 찾는 알고리즘입니다.

 

이 문제는 완전 탐색, 부분합 수열, 분할 정복, DP 를 활용하여 풀 수 있지만 각각 시간 복잡도가 O(2^n), O(n^2), O(nlogn), O(n) 로 다르기 때문에 가장 효율적인 DP로 푸는것이 가장 바람직합니다. 

 

# 예제 코드

def getSum(arr):
    dp = sequence[0]	# 현재까지의 최대합
    cur = 0				# 실시간 최대합
    
    for x in arr:
        cur = max(x, cur + x)		# 특정 구간까지의 합 + 현재 값 vs 현재 값
        dp = max(dp, cur)			# cur이 현재까지 최대합보다 크다면 갱신
        
    return dp

 

 

 

# 알고리즘의 쓰임

1. 주식 거래: 주식 시장에서는 주가의 변동으로 인해 이익과 손실이 발생할 수 있습니다. 최대 부분 배열 합 알고리즘은 특정 기간 동안의 주식 가격 데이터에서 최대 수익을 얻을 수 있는 구간을 찾는 데에 활용될 수 있습니다.
   
   
2. 프로젝트 관리: 프로젝트 진행 중에는 여러 작업들이 필요하며, 각 작업의 소요 시간과 비용이 다를 수 있습니다. 최대 부분 배열 합 알고리즘은 작업들을 어떤 순서로 수행해야 최대 이익(시간, 비용, 효율성 등)을 얻을 수 있는지 결정하는 데에 사용될 수 있습니다.
   
   
3. 자원 관리: 자원이 제한적인 환경에서 자원의 사용량과 이익(예: 수익, 생산량) 사이의 상관 관계를 고려할 때, 최대 부분 배열 합 알고리즘은 최대 이익을 얻을 수 있는 자원 사용 패턴을 찾는 데에 활용될 수 있습니다.
   
   
4. 광고 및 마케팅 전략: 광고 노출에 따른 고객의 반응이나 판매량과 같은 데이터를 분석하여 최대의 효과를 가져올 수 있는 광고 및 마케팅 전략을 찾는 데에 최대 부분 배열 합 알고리즘이 활용될 수 있습니다.
   
   
5. 자연어 처리: 텍스트 데이터에서 단어나 문장의 길이나 빈도와 같은 특성을 고려하여 최대로 유의미한 부분 텍스트를 추출하는 데에 최대 부분 배열 합 알고리즘이 활용될 수 있습니다.

 

 

 

 

# references

https://shoark7.github.io/programming/algorithm/4-ways-to-get-subarray-consecutive-sum  

https://chanhuiseok.github.io/posts/improve-4/

chatgpt