최대 부분 배열 합의 효율성 측정하기

n개의 정수로 이루어진 임의의 수열이 주어지고, 수를 한 개 이상 선택하여 연속된 부분 수열의 합들 중 최대값을 구하려고 한다.

 

BOJ(1912) : 연속합 문제에서는 n이 1~100000 이므로 O(NlogN) 또는 O(N)으로 풀어야하므로 dp를 풀어서 해결하여야 합니다.

 

O(N^3) 풀이 : n이 10이하일 때 가능

let best = 0;
for(let i=0; i<n; i++){
    for(let j=i; j<n; j++){
        let sum=0;
        for(let k=i; k<=j; k++){
            sum+=arr[k];
        }
        best=Math.max(best, sum);
    }
}
console.log(best);

 

O(N^2) 풀이 :n이 5000이하일 때 가능

let best = 0;
for(let i=0; i<n; i++){
    let sum=0;
    for(let j=i; j<n; j++){
        sum+=arr[j];
        best=Math.max(best, sum);
    }
}
console.log(best);

 

O(N) 풀이(DP)

• 위치 k에서 끝나면서 합이 최대인 부분 배열을 구하는 부분 문제는 단 2가지입니다.
  • 부분 배열이 위치 k의 원소 하나만일 때
  • 위치 k-1에서 끝나는 부분 배열에, 위치 k의 원소를 덧붙여 부분 배열을 만들 때

따라서  이렇게 sum에는 “위치 k-1까지의 합 + 위치 k의 원소” 혹은 “위치 k 원소 하나의 값” 둘 중 더 큰 것이 들어가게 됩니다.

sum에 둘 중 하나의 값을 선택하기 전, sum + array[k]에서의 sum에는 자연스레 위치 k-1까지의 합이 들어가 있게 됩니다.

위의 수열을 예시로 차례대로 살펴보면

 

-1(sum = -1, best = -1)

max( (-1+2), 2)  => 1<2 이므로 -1은 부분 배열에서 삭제가 되고 2부터 다시 시작합니다. (sum = 2, best = 2)

max( (2+4), 4) => 6>4 이므로 부분배열에 넣어서 진행합니다. (sum = 6, best = 6)

max( (6-3), -3) => 3>-3 이므로 부분배열에 넣어서 진행합니다. (sum = 3, best = 6)

max( (3+5), 5) => 8>5 이므로 부분배열에 넣어서 진행합니다. (sum = 8, best = 8)

max( (8+2), 2) => 10>2 이므로 부분배열에 넣어서 진행합니다. (sum = 10, best = 10)

max( (10-5), -5) => 5>-5 이므로 부분배열에 넣어서 진행합니다. (sum = 5, best = 10)

max( (5+2), 2) => 7>2 이므로 부분배열에 넣어서 진행합니다. (sum = 7, best = 10)

 

따라서 최대값을 10입니다.

원소의 개수가 8개이고, 비교도 8번 했으므로 모든 원소를 적어도 한번 씩 탐방하여 문제를 해결하였으므로 시간복잡도 O(N)에 해당합니다.

 

let best = arr[0];
let sum=0;
for(let i=0; i<n; i++){
    sum=Math.max(arr[i],sum+arr[i]);
    best=Math.max(sum,best);
}
console.log(best);

 

 

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