[Codility] Chapter 9. Maximum slice problem, 최대 구간 문제

Reference: https://codility.com/media/train/7-MaxSlice.pdf 

 

 코딜리티 알고리즘 학습 pdf 중에서 나중에 써먹을 만한 것

 

최대 슬라이싱과 관련된 문제를 정의해 본다. n 개의 정수 배열이 주어지고, 가장 큰 합을 갖는 구간을 찾는 일이다. 더 정확히는, 두개의 인덱스 p, q 를 찾는데, [p]~ [q] 까지의 합이 최대값인 것이다. 예를 들어, p = 2, q = 5 가 최대 슬라이스 구간의 합을 찾은 것이다.

 

 

단순하게 O(n^3) 시간복잡도를 갖는 풀이를 생각 해볼 수 있다.

 

1. n개의 정수 배열 입력받는다.

2. 앞쪽 인덱스 p 는 0~ n 반복한다.

 2.1. 뒤쪽 인덱스 q 는 p~ n 반복한다.  ->  여기까지의 반복이 모든 경우의 슬라이싱 구간을 만들어낸다.

  2.1.1. 이제 p~ q 슬라이싱의 합을 구한다.

  2.1.2. 기존 최대값과 비교 갱신 한다.

3. 최대값 반환한다.

-> 이건 뭐.. 그냥 대충 머리로 구현을..

 

 

O(n^2) 시간복잡도를 갖는 풀이로 최적화 해볼 수 있다.

1. n개의 정수 배열 입력받는다.

2. 앞쪽 인덱스 p 는 0~ n 반복한다.

 2.1. 슬라이싱 합 초기화 한다.

 2.2. 뒤쪽 인덱스 q 는 p~ n 반복한다.

  2.2.1. 기존 슬라이싱 합에 [q] 값을 더한다.

  2.2.2. 기존 최대값과 비교 갱신한다.

3. 최대값 반환한다.

    public int maxSliceQuadratic(int[] a) {
        int n = a.length;
        int result = 0;
        int sum;

        for (int i = 0; i < n; ++i) {
            sum = 0;
            for (int j = i; j < n; ++j) {
                sum += a[j];
                result = Math.max(result, sum);
            }
        }

        return result;
    }

 

 

O(n) 시간복잡도를 갖는 풀이로 최적화 해볼 수 있다.

1. n개의 정수 배열 입력받는다.

2. 정수 배열 전체 반복한다.

 2.1. 이전 누적 합 중 최대 값 (직전의 값까지의 누적 최대합에 이번 차례 값을 더함)

 2.2. 최대 슬라이싱 합은 기존 최대합과 이전 누적합을 비교 갱신한다.

3. 최대값 반환한다.

    public int maxSlice(int[] a) {
        int maxEnding = 0;
        int maxSlice = 0;

        for (int i = 0; i < a.length; ++i) {
            maxEnding = Math.max(0, maxEnding + a[i]);
            maxSlice = Math.max(maxSlice, maxEnding);
        }

        return maxSlice;
    }