19. maximum subarray [10 1주차]

19. Maximum Subarray [10-1주차]

2024년 1월 14일 일요일

오전 2:26

<Maximum Subarray 문제>

정수(음수 포함)들의 배열에서 연속된 부분 배열을 합이 최대가 되도록 찾는 문제이다.

부분배열의 길이가 0인 경우를 허용하는 경우, 허용하지 않는 경우에 따라 답을 구하는 방법이 살짝 달라진다.

<O(n³) 풀이>

모든 경우를 다 찾아 비교하면 된다.

만들어질 수 있는 부분 배열은 약 _nC₂가지, O(n²)개이다. 부분 배열 하나의 합을 계산하는 데 최대 O(n)시간이 걸리므로, 총 O(n³)이 걸린다.

<O(n²) 풀이>

부분 배열의 합을 구할 때 중복 계산을 줄인다. 이전에 구했던 더 작은 부분 배열에 원소를 더하면 된다.

<O(n) 풀이 : Idea 1>

0<= i < n

i에서 끝나는 합이 가장 큰 부분 배열의 합을 S[i]라 한다.

S[i+1]이 될 수 있는 값은 S[i]+A[i+1] 또는 A[i+1]뿐이다.

S[i] ≠ A[a…i]일 때, A[a…i] + A[i+1]이 가장 클 순 없다. A[a…i]를 S[i]로 바꾸면 더 커지기 때문.

S[i+1] = max(S[i] + A[i+1], A[i+1])

<Idea 2>

A[i]를 포함하는 최대 부분 배열의 합과 A[i]를 포함하지 않는 최대 부분 배열의 합을 0<=i<n마다 각각 구한다.

<Idea 3>

Prefix sum 배열 B를 이용하는 방법.

A[0]부터 A[i]까지의 합의 배열 B를 구한다.

k < i이고, B[k]가 가장 작도록 하는 인덱스 k를 찾는다.

그러면 S[i] = B[i] - B[k]이다.