절묘 한 알고리즘 - 최대 하위 서열 과 문제

문제 의 도입
    주어진 (음수 가 있 을 수 있 음) 정수 서열 A1, A2, A3..., An, 이 서열 의 중성자 서열 과 최대 치 를 구하 십시오.(편 의 를 위해 모든 정수 가 마이너스 라면 가장 큰 하위 서열 과 0).예 를 들 어 정수 서열 을 입력 하 십시오. - 2, 11, 8, - 4, - 1, 16, 5, 0 이면 출력 답 은 35, 즉 A2 ～ A6 입 니 다.
    이 문제 가 매력 적 인 이 유 는 주로 그것 을 푸 는 많은 알고리즘 이 존재 하기 때문에 이런 알고리즘 들 의 성능 차이 가 매우 크다.이런 알고리즘 들 은 소량의 입력 에 대한 차이 가 크 지 않 고 몇 개의 알고리즘 이 모두 순간 에 완 성 될 수 있다. 이때 대량의 노력 을 들 여 똑똑 한 알고리즘 을 설계 하면 가치 가 없 을 것 이다.그러나 대량의 입력 에 대해 처리 결 과 를 빨리 얻 으 려 면 디자인 이 좋 은 알고리즘 이 필요 하 다.
본론 으로 들어가다
    다음은 먼저 디자인 에 가장 시간 이 걸 리 지 않 는 알고리즘 을 제공 합 니 다. 이 알고리즘 은 디자인 하기 쉽 고 이해 하기 쉽 지만 대량의 입력 에 있어 효율 이 너무 낮 습 니 다.
    알고리즘 1:

public static int maxSubsequenceSum(int[] a) {
    int maxSum = 0;
    for(int i=0; i<a.length; i++) {        //i        
        for(int j=i; j<a.length; j++) {    //j        
            int thisSum = 0;
            for(int k=0; k<=j; k++)        //            ，  
                thisSum += a[k];
            if(thisSum > maxSum)
                maxSum = thisSum;
        }
    }
    return maxSum;
}

    상술 한 설 계 는 이해 하기 쉽다. 그것 은 단지 각종 가능 한 결 과 를 궁리 하고 마지막 에 가장 큰 하위 서열 과 결 과 를 얻 을 뿐이다.의심 할 여지없이 이 알고리즘 은 정확하게 화 해 를 낼 수 있 지만, 만약 에 어떤 하위 서열 인지 더 얻어 야 한다 면, 이 알고리즘 은 추가 코드 를 추가 해 야 한다.
    이제 다음 알고리즘 의 시간 복잡 도 를 분석 해 보 겠 습 니 다.실행 시간의 많 고 적 음 은 6, 7 줄 에 달 려 있 습 니 다. 세 번 째 줄 의 순환 크기 는 N 이 고 네 번 째 줄 의 순환 크기 는 N - i 입 니 다. 작 을 수도 있 지만 N 일 수도 있 습 니 다.우 리 는 시간의 복잡 도 를 판단 할 때 반드시 최 악의 상황 을 취해 야 한다.여섯 번 째 줄 의 순환 크기 는 j - i + 1 이 고 우 리 는 그것 의 크기 를 N 이 라 고 가정 해 야 한다.따라서 총 수 는 O (1 * N * N * N) = O (N3) 다.두 번 째 줄 의 총 지출 은 O (1) 이 고 8, 9 줄 의 총 지출 은 O (N2) 입 니 다. 두 층 순환 내부 의 간단 한 표현 식 이기 때 문 입 니 다.
    우 리 는 for 순환 을 철거 함으로써 세 번 의 운행 시간 을 피 할 수 있다.그러나 이것 은 항상 가능 한 것 이 아니다. 이런 상황 에서 알고리즘 에 대량의 불필요 한 계산 이 나타난다.이러한 비효 율 적 인 개선 알고리즘 을 바로 잡 는 것 은 Sum (Ai ~ Aj) = Aj + Sum (Ai ~ A [j - 1]) 을 관찰 해 볼 수 있 기 때문에 알고리즘 1 중 6, 7 줄 의 계산 이 지나치게 소모 되 었 다.다음은 알고리즘 1 을 바탕 으로 개 선 된 알고리즘 입 니 다.
    알고리즘 2:

public static int maxSubsequenceSum(int[] a) {
    int maxSum = 0;
    for(int i=0; i<a.length; i++) {
        int thisSum = 0;
        for(int j=i; j<a.length; j++) {
            thisSum += a[j];
            if(thisSum > maxSum)
                maxSum = thisSum;
        }
    }
    return maxSum;
}

    이 알고리즘 에 대해 시간 복잡 도 는 분명히 O (N2) 이 고 그 에 대한 분석 은 앞의 분석 보다 더 간단 하 다. 즉, 빈 거 법 으로 서열 중의 i 뒤의 모든 값 을 추가 하 는 것 이다. 만약 에 max Sum 보다 큰 것 을 발견 하면 max Sum 의 값 을 업데이트 하 는 것 이다.
    이 문제 에 대해 서 는 재 귀 와 상대 적 으로 복잡 한 O (NLogN) 해법 이 있 습 니 다. 우 리 는 지금 그것 을 설명 하 겠 습 니 다.만약 에 O (N) (선형) 해법 이 나타 나 지 않 았 다 면 이 알고리즘 은 재 귀 사례 를 나타 내 는 좋 은 범례 가 될 것 이다.이 방법 은 일종 의 분 치 전략 을 채택 한다.그 생각 은 그 렇 죠? 문 제 는 대체적으로 같은 두 개의 서브 문제 로 나 뉘 어 재 귀적 으로 그들 에 게 답 을 구 하 는 것 이 '분' 의 단계 입 니 다.'치' 단 계 는 두 가지 문제 의 해 를 함께 보완 하고 소량의 부가 작업 을 해서 마지막 에 전체 문제 의 해 를 얻 는 것 이다.
    우리 의 예 에서 가장 큰 하위 서열 의 합 은 세 곳 에 만 나타 날 수 있다.

입력 데이터 의 왼쪽 부분 에 나타난다

입력 데이터 의 오른쪽 부분 에 나타난다

입력 데이터 의 중 부 를 뛰 어 넘 고 좌우 두 부분

    앞의 두 가지 상황 은 재 귀적 으로 해석 할 수 있다. 세 번 째 상황 의 최대 와 전반 부 (전반 부 를 포함 한 마지막 요소) 의 최대 와 후반 부 (후반 부 를 포함 한 첫 번 째 요소) 의 최대 화 를 구 한 다음 에 두 가 지 를 더 할 수 있다.예 를 들 어 다음 과 같은 입력 을 고려 합 니 다.

-----------------------------------------
                         
-----------------------------------------
-2, 11, 8, -4,    -1, 16, 5, 0   
-----------------------------------------

    그 중에서 앞부분 의 최대 자 서열 과 19 (A2 ~ A3) 이 고 후반 부의 최대 자 서열 과 21 (A6 ~ A7) 이다.앞부분 에는 마지막 원소 의 최대 와 15 (A2 ~ A4) 가 포함 되 어 있 고, 후반 부 에는 첫 번 째 원소 의 최대 와 20 (A5 ~ A7) 이 포함 되 어 있다.따라서 이 두 부분 을 뛰 어 넘 는 이 하위 서열 이 야 말로 가장 큰 하위 서열 을 가 진 것 이 고 15 + 20 = 35 (A2 ～ A7) 이다.그래서 다음 알고리즘 이 나 왔 습 니 다.
    알고리즘 3:

public static int maxSubsequenceSum(int[] a, int left, int right) {
    if(left == right) { //Base case
        if(a[left] > 0) {
            return a[left];
        } else {
            return 0; //      0
        }
    }
    
    int center = (left+right)/2;
    int maxLeftSum = maxSubsequenceSum(a, left, center); //    ，        
    int maxRightSum = maxSubsequenceSum(a, center+1, right);//    ，        
    
    int leftBorderSum = 0, maxLeftBorderSum = 0;//          
    for(int i=center; i>=left; i--) {
        leftBorderSum += a[i];
        if(leftBorderSum > maxLeftBorderSum) {
            maxLeftBorderSum = leftBorderSum;
        }
    }
    
    int rightBorderSum = 0, maxRightBorderSum = 0;//          
    for(int i=center+1; i<=right; i++) {
        rightBorderSum += a[i];
        if(rightBorderSum > maxRightBorderSum) {
            maxRightBorderSum = rightBorderSum;
        }
    }
    
    //             （max3(int a, int b, int c)       ）
    return max3(maxLeftSum, maxRightSum, maxLeftBorderSum + maxRightBorderSum);
}

    알고리즘 3 의 프로그램 에 대해 약간의 설명 을 할 필요 가 있다.재 귀 프로 세 스 호출 의 일반적인 형식 은 입력 한 배열 과 좌우 경 계 를 전달 하 는 것 으로 배열 이 처리 해 야 할 부분 을 정의 했다.제2 ~ 8 행 처리 기준 상황 은 재 귀적 호출 에 퇴출 의 기 회 를 준다.만약 left = = right 라면 하나의 요소 만 있 고 이 요소 가 마이너스 가 아 닐 때 가장 큰 하위 서열 입 니 다.제1 1, 12 행 은 두 개의 재 귀적 호출 을 집행 한다.우 리 는 재 귀적 호출 이 항상 원래 문제 보다 작은 문제 에 대해 진행 되 는 것 을 볼 수 있 지만, 프로그램의 작은 스 포일 러 는 이 특성 을 파괴 할 수 있다.14 ～ 20 줄, 22 ～ 28 줄 의 경계 에서 좌우 양쪽 의 가장 큰 하위 서열 과 이 두 값 의 합 은 전체 서열 중의 가장 큰 하위 서열 과 일 수 있다.제3 1 줄 에서 max 3 방법 을 호출 하여 이 세 가지 상황 에서 의 최대 치 를 구하 십시오. 이 값 은 전체 서열 의 가장 큰 하위 서열 과 같 습 니 다.
    분명 한 것 은 알고리즘 3 은 디자인 전 두 가지 알고리즘 보다 더 많은 프로 그래 밍 노력 을 기울 여야 한다. 앞의 두 가지 알고리즘 의 코드 량 이 알고리즘 3 보다 훨씬 적은 것 처럼 보이 지만 프로그램 이 짧다 는 것 은 프로그램 이 좋다 는 것 을 의미 하지 않 는 다.테스트 결과 에 따 르 면 비교적 작은 입력 량 을 제외 하고 알고리즘 은 앞의 두 알고리즘 보다 현저히 빠르다.이제 다음 알고리즘 3 의 시간 복잡 도 를 분석 해 보 겠 습 니 다.
    령 T (N) 는 크기 가 N 인 가장 큰 하위 서열 과 문 제 를 푸 는 데 걸 리 는 시간 이다.N = 1 이면 알고리즘 3 실행 프로그램의 2 ~ 8 줄 에 상수 시간 이 걸 리 는데 우 리 는 이 를 하나의 시간 단위 라 고 부른다.따라서 T (1) = 1, 그렇지 않 으 면 프로그램 은 14 ~ 28 줄 사이 의 두 개의 for 순환 과 몇 개의 작은 부 기 량, 예 를 들 어 10, 14 줄 등 두 개의 재 귀적 호출 을 실행 해 야 한다.이 두 for 순환 은 모두 A1 ~ An 의 모든 요 소 를 접 하고 순환 내부 의 작업량 은 상수 이기 때문에 14 ~ 28 줄 에 걸 리 는 시간 은 O (N) 이다.2 ~ 10, 14, 22, 31 줄 의 프로그램의 작업량 은 상수 이 므 로 O (N) 에 비해 무시 할 수 있 습 니 다.나머지 는 11 ~ 12 줄 에서 운행 하 는 작업 만 남 았 다.이 두 줄 의 크기 가 N / 2 인 하위 서열 문제 (N 을 짝수 로 가정).따라서 이 두 줄 은 줄 당 T (N / 2) 개의 시간 단원 을 쓰 고 모두 2T (N / 2) 개의 시간 단원 을 쓴다.따라서 알고리즘 3 에 걸 리 는 총 시간 은 2T (N / 2) + O (N) 이다.그래서 우 리 는 방정식 조 를 얻 었 다.

T(1) = 1
T(N) = 2T(N/2) + O(N)

    계산 을 간소화 하기 위해 서 우 리 는 위의 방정식 중의 O (N) 항 을 N 으로 대체 할 수 있다.T (N) 는 결국 대 O 로 표시 해 야 하기 때문에 이렇게 하 는 것 은 답 에 영향 을 주지 않 는 다.지금 T (N) = 2T (N / 2) + N, 그리고 T (1) = 1 이 라면 T (2) = 4 = 2 * 2;T(4) = 12 = 4*3；T(8) = 32 = 8*4；T(16) = 80 = 16*5。수학 적 귀납법 으로 N = 2 ^ k 이면 T (N) = 2 ^ k * (k + 1) = N * (k + 1) = N (logN + 1) = N logN + N = O (NLogN) 를 증명 할 수 있다.즉, 알고리즘 3 의 시간 복잡 도 는 O (NLogN) 로 알고리즘 2 의 복잡 도 O (N2) 보다 현저히 작 기 때문에 알고리즘 3 은 더 빨리 결 과 를 얻 을 수 있다.
    이 분석 은 N 이 짝수 라 고 가정 한다. 그렇지 않 으 면 N / 2 가 확실 하지 않다.이 분석의 재 귀 성질 을 통 해 알 수 있 듯 이 실제 적 으로 N 이 2 의 멱 일 때 만 결과 가 합 리 적 인 것 이다. 그렇지 않 으 면 우 리 는 결국 크기 가 짝수 가 아 닌 서브 문 제 를 얻 게 되 고 방정식 은 무효 이다.N 이 2 의 멱 이 아 닐 때 우 리 는 다소 더 복잡 한 분석 이 필요 하지만 대 O 의 결 과 는 변 하지 않 는 다.
더 우수한 알고리즘
    알고리즘 3 은 충분히 우수 하고 시간 복잡 도 를 O (N2) 에서 O (NLogN) 로 낮 추 었 지만 이것 이 가장 우수한 것 이 아니 라 이 문제 에 대한 더욱 우수한 해법 을 소개 한다.
    알고리즘 4:

public static int maxSubsequenceSum(int[] a) {
    int maxSum = 0, thisSum = 0;;
    for(int i=0; i<a.length; i++) {
        thisSum += a[i];
        if(thisSum > maxSum)
            maxSum = thisSum;
        else if(thisSum < 0)
            thisSum = 0;
    }
    return maxSum;
}

    분명 한 것 은 이 알고리즘 의 시간 복잡 도 는 O (N) 이 고 이것 은 알고리즘 3 중의 시간 복잡 도 O (NLogN) 보다 작 기 때문에 이 알고리즘 은 알고리즘 3 보다 더욱 빠르다!방법 은 이미 제시 되 었 지만 왜 이 방법 을 사용 할 수 있 는 지 알 기 위해 서 는 더 많은 생각 이 필요 하 다.
    알고리즘 1 과 알고리즘 2 에서 i 는 하위 서열 의 출발점 을 대표 하고 j 는 하위 서열 의 종점 을 대표 한다.공교롭게도 우 리 는 구체 적 으로 가장 좋 은 하위 서열 이 어디 에 있 는 지 알 필요 가 없다. 그러면 i 의 사용 은 프로그램 에서 최적화 될 수 있 기 때문에 알고리즘 을 설계 할 때 i 가 필요 하 다 고 가정 하고 우 리 는 알고리즘 2 를 개선 하고 싶다.하나의 결론 은 a [i] 가 마이너스 라면 가장 좋 은 서열 의 출발점 을 대표 할 수 없다 는 것 이다. 왜냐하면 a [i] 를 포함 하 는 출발점 의 하위 서열 은 a [i + 1] 을 기점 으로 개선 할 수 있 기 때문이다.유사 한 것 은 그 어떠한 마이너스 서열 도 가장 좋 은 하위 서열 의 접두사 (원리 가 같다) 일 수 없다.내부 순환 에서 a [i] 에서 a [j] 까지 의 하위 서열 의 합 이 음수 가 검출 되면 뒤로 i 를 추진 할 수 있 습 니 다.관건 적 인 결론 은 i + 1 까지 추진 할 수 있 을 뿐만 아니 라 실제로 우 리 는 j + 1 까지 추진 할 수 있다 는 것 이다.이 점 을 똑똑히 보기 위해 서, 우 리 는 p 를 i + 1 과 j 사이 의 임의의 표 시 를 하도록 합 니 다.아래 표 시 된 p 의 임의의 하위 서열 은 아래 표 시 된 i 보다 크 지 않 고 a [i] 에서 a [p - 1] 까지 의 하위 서열 에 대응 하 는 하위 서열 을 포함 합 니 다. 왜냐하면 뒤에 있 는 이 하위 서열 은 마이너스 가 아니 기 때 문 입 니 다. (즉, j 는 아래 표 시 된 i 부터 그 값 은 마이너스 서열 의 첫 번 째 아래 표 가 됩 니 다)따라서 i 를 j + 1 로 추진 하 는 것 은 위험 이 없다. 우 리 는 가장 잘 풀 어도 놓 치지 않 는 다.
    이 알고리즘 은 많은 똑똑 한 알고리즘 의 전형 이다. 운행 시간 은 뚜렷 하지만 정확성 은 쉽게 알 아 볼 수 없다.이러한 알고리즘 에 대해 정식 적 인 정확성 증명 (위의 분석 보다 더욱 정식 적) 은 거의 항상 필요 하 다.그러나 그때 가 되 어도 많은 사람들 이 믿 지 않 았 다.그 밖 에 많은 이런 알고리즘 은 더욱 기교 있 는 프로 그래 밍 을 필요 로 하기 때문에 더욱 긴 개발 과정 을 초래한다.그러나 이 알고리즘 들 이 정상적으로 작 동 할 때, 그것들 은 매우 빨리 작 동 합 니 다!우 리 는 그것들 을 저 효율 이지 만 실현 하기 쉬 운 만력 알고리즘 과 소 규모 입력 을 통 해 대부분의 프로그램 원 리 를 비교 할 수 있다.
    이 알고리즘 의 장점 중 하 나 는 데 이 터 를 한 번 스 캔 하면 a [i] 가 읽 히 고 처리 되면 기억 되 지 않 아 도 된다 는 것 이다.따라서 배열 이 디스크 에서 네트워크 를 통 해 전송 된다 면 순서대로 읽 을 수 있 고 메 인 저장 소 에 배열 의 어떤 부분 도 저장 하지 않 아 도 된다.뿐만 아니 라 임의의 시간 에 알고리즘 은 이미 읽 은 데이터 에 대해 하위 서열 문제 의 정 답 을 제시 할 수 있다 (다른 알고리즘 은 이 특성 을 갖 추 지 않 는 다).이런 특성 을 가 진 알고리즘 을 온라인 알고리즘 이 라 고 한다.상수 공간 만 필요 하고 선형 시간 으로 실행 되 는 온라인 알고리즘 은 거의 완벽 한 알고리즘 이다.