[ 알고리즘 ] Dynamic Programming : Maximum Subarray

1. 문제 정의

 

각 칸에 숫자가 적혀있을 때, 합이 최대가 되게 하는 Subarray의 합을 구하는 것이다. 

0칸의 합도 허용하는 버전과, 허용하지 않는 버전 모두 소개될 것이다. 

 

2. idea : O(N^3)

1.모든 경우의 수를 다 해본다. 

크기가 1인거 n개, 2인거 n-1개,...,n인거 1개 → n(n-1)/2  => (N^2)

한 시행이 걸리는 시간 N. 쭉 훑으면서 더해야하기 때문.

 

2. 칸을 나누는 선은 n+1개 이다. 이 중 시작선과 끝선을 두개 뽑는다 n+1C2 => (N^2)

한 시행이 걸리는 시간 N. 쭉 훑으면서 더해야하기 때문.

 

3. idea : O(N^2)

아이디어는 앞에와 같다. 이 방법은 계산에 쓰이는 시간 N을 절약하는 것이다. 

n개가 계산이 되어어있고 n+1개를 계산해야한다면, n개 계산 되어있는것에 하나만 더하면된다. 

 

4. idea : O(N)

답을 도출할 때 0칸의 합도 정답으로 쳐주냐에 따라 답이 다를 수 있다. 

0칸의 합은 0이다.

하지만 n개의 칸의 합이 음수고 이것이 최대라면 그 답을 도출하는 것보다 0칸인 0을 도출하는것이 더 크다.

 

4.1 idea(1)

 

각 칸에 그 자리에서 끝나는 가장 큰 합을 적는 방법이다. 

그렇다면 어떻게 효율적으로 그 자리에서 가장 큰 합을 찾을 수 있을까?

 

i번 째를 생각하면, 이 때 i-1번째의 최대값은 이미 적혀있다. 

i번 째의 최대값은 아래의 값 중 최대값을 적으면 된다. 

 

1) 0칸 허용 X

• i 번째 값
• i-1의 최대값 + i번째 값

2) 0칸 허용

• 0
• i-1의 최대값 + i번째 값

 

4.2 idea(2)

아이디어1과 비슷한데, 관점만 살짝 다른 느낌이다.

 

인덱스 i번차례에서 나를 포함하는 최대값과 나를 포함하지 않는 최대값을 비교하는 것이다.

 

1) 0칸 허용 X

1. i일 때 답 S[i]
2. S[i+1] = max( S[i]+A[i+1] , A[i+1] )
3. S[i+1] = max( S[i] , S[i+1] )

2) 0칸 허용

1. i일 때 답 S[i]
2. S[i+1] = max( S[i]+A[i+1] ,0 )
3. S[i+1] = max( S[i] , S[i+1] )

 

4.3 idea(3) : Prefix Sum

 

부분합 Pi를 처음부터 Ai까지 더한 합이라고 하자.

그럼 i번에서의 정답은 max(Pi - Pi-1, Pi - Pi-2, ..., Pi - P0) 이다.

min(Pi-1, Pi-2, ..., P0$)을 찾아서 빼면 된다. max를 구할 수 있다. 

0칸을 고려한다면 Pi - Pi를 허용하면 된다.