동적 계획법 practice_02 가장 큰 부분 합 찾기

- 엘리스 자료구조의 정석) 문제

 

가장 큰 부분합 찾기

 

정수들의 리스트가 입력으로 들어옵니다. 이 정수들의 리스트를 일부분만 잘라내어 모두 더했을 때의 값을 부분합이라 부릅니다. 이때 가장 큰 부분합을 구해봅시다.

예를 들어, [-10, -7, 5, -7, 10, 5, -2, 17, -25, 1]이 입력으로 들어왔다면 [10, 5, -2, 17]을 모두 더한 30이 정답이 됩니다.

※입력에는 최소 하나 이상의 양수가 존재합니다.

※이 문제에는 여러 종류의 풀이법이 존재합니다. 각 풀이법의 시간 복잡도를 고려하면서 여러가지 방법으로 문제를 풀어 봅시다.

 

 

- 코드

 
def maxSubArray(nums):
   
   s=0
   result=0
   for i in nums:
       s+=i
       result=max(result,s)
       if s<0:
           s=0
   return result
 
 
def main():
    print(maxSubArray([-10, -7, 5, -7, 10, 5, -2, 17, -25, 1])) # 30이 리턴되어야 합니다
 
if __name__ == "__main__":
    main()

 

- 이번 알고리즘을 통해 배운 점

 

이번 문제는 "최소 하나이상의 양수가 존재한다 " 가 핵심인 것 같다. 누적 할 s변수와 결과값을 저장할 result를 비교하는 것이 이 문제를 풀어나가는 방법이다. 앞서 말한것처럼 하나 이상의 양수가 존재하므로 누적한 값이 음수면(if s<0) 앞에 값들은 해당하지 않는다는 말이므로 누적값에 0을 넣어(s=0) 재탐색을 시작한다. 

이후 양수를 찾게 되면 result에 저장하게 되고 값을 비교하고 누적하여 가장 큰 부분을 찾는다.

 

예시를 들겠다. maxSubArray([-10, -7, 5, -7, 10, 5, -2, 17, -25, 1])

maxSubArray 에서 앞에 음수들은 지나치게 되고 양수인 5를 만나 result에 저장한다. 

 

이후 음수 -7을 만난다. 더하여 -2가 나오므로 현재 가장 큰 부분인 (5)를 result에 저장하고

누적값은 음수이므로 0이 되어 재탐색을 시작한다.

 

이후 (10,  5) 부분에서 15를 누적하게 되고 현재 가장 큰 부분은 (10,5) 가 된다.

 

이후 음수 -2 를 만난다. 더하여 13이 나오므로 현재 가장 큰 부분인(10,5)를 result에 저장하고

누적값은 현재 음수가 아니고 뒤에 더 큰 숫자가 있을지도 모르니 그대로 값을 가지고 있는다.

 

이후 양수 17를 만난다.  더하여 30이 나오므로 현재 가장 큰 부분인 (10,5,-2,17)를 result에 저장하고

누적값은 현재 음수가 아니고 뒤에 더 큰 숫자가 있을지도 모르니 그대로 값을 가지고 있는다. .

 

반복 ... 

이렇게  반복문을 다 돌면 가장 큰 부분합을 찾을 수 있게 된다.