[leetcode] 53. Maximum Subarray

Maximum Subarray - LeetCode

Maximum Subarray - LeetCode

문제설명

배열이 주어졌을 때 subarray 중에 최대 합을 구하는 문제이다.

풀이

1. 시간 복잡도 O(NlogN) 풀이 : Divide and Conque

배열의 가운데 원소를 중심으로 왼쪽 배열과 오른쪽 배열을 생각해보자. 이 때 생각해 볼 수 있는 maximum subarrya의 형태는

1. 왼쪽 배열에만 있거나

2. 오른쪽 배열에만 있거나

3. 왼쪽배열과 오른쪽 배열을 걸쳐있는 형태일 것이다.

 따라서 왼쪽 배열의 maximum subarray 와 오른쪽 배열의 maximum subarray 그리고 걸쳐있는 배열 중에 그 합이 maximum이 되는 배열들을 비교하면 된다. 왼쪽 배열과 오른쪽 배열의 maximum subarray를 구하기 위해 위와 같은 논리를 왼쪽 배열과 오른쪽 배열에 대해 똑같이 적용하면 된다.(재귀적으로) 즉, divide and conquer 문제가 된다.

2. 시간 복잡도 O(N)  풀이: DP(tabulation)

이 때 sub-problem은 i번째 index로 끝나는 sub-array 중에 최대합을 가지는 배열을 구한 다음,

그 중에서 최대합을 가지는 값을 return 하면 된다.

구현

 i 번째 index로 끝나는 subarray 중에 최대합을 가지는 배열은 i-1번째로 인덱스 끝나는 subarray에 i번째 원소를 더하거나 i번째 원소만을 가지는 subarray 둘 중 하나일 것이다.

이를 흔히 Kadane 알고리즘이라고도 한다.

 

DP와 Divide And Conquer의 차이

1. DP는 subproblem의 solution이 optimal solution의 일부가 된다.

ex) binary search는 DP로 풀 수 없다

2. DP는 subproblem을 재사용하는 경우가 있다.