최대 하위 열 과 문제 풀이 - MaxSubSum

가장 큰 하위 열 과 문 제 를 푸 는 데 는 여러 가지 방법 이 있다. 가장 간단 하고 거 친 방법 은 모든 하위 열 을 찾 아 하위 열 과 최대 하위 열 을 계산 하 는 것 이다. 그러나 이런 방법 은 효율 이 매우 낮다.효율 적 이 고 빠 르 며 교묘 하 게 최대 하위 열 을 풀 려 면 더 좋 은 방법 을 고려 해 야 한다.
       '나 누 어 다스 리 는 것' 은 바로 이 문 제 를 해결 하 는 기본 사상 이다. 모든 하위 열 에서 최대 하위 열 과 전체 가 입력 데이터 의 왼쪽 부분 에 나타 날 수도 있 고 전체 가 오른쪽 부분 에 나타 날 수도 있 으 며 입력 데이터 의 중 부 를 넘 어 왼쪽 부분 과 반 부분 을 차지 할 수도 있다.
       앞의 두 가지 상황 에서 우 리 는 재 귀적 인 방식 으로 좌우 두 부분 을 여러 번 나 누 어 두 개의 데이터 만 비교 할 때 까지 차례대로 비교적 큰 하위 열 과 를 되 돌려 왼쪽 부분 과 오른쪽 부분의 최대 하위 열 과 를 구 할 수 있다.
세 번 째 는 왼쪽 과 오른쪽 을 뛰 어 넘 는 경우 왼쪽 부분의 최대 와 (왼쪽 의 마지막 요 소 를 포함), 오른쪽 부분의 최대 와 (오른쪽 첫 번 째 요 소 를 포함) 를 구 한 다음 에 이 두 가 지 를 더 할 수 있다.
그 다음 에 왼쪽 최대 하위 열 과 오른쪽 최대 하위 열 을 비교 하고 중부 최대 하위 열 과 를 뛰 어 넘 어 이 입력 데이터 의 최대 하위 열 과 를 구 합 니 다.
예제 프로그램 은 다음 과 같다.

//
//  main.c
//       
//
//  Created by     on 16/4/11.
//  Copyright © 2016  Wuyuan. All rights reserved.
//

#include 

/**
 *  find a max integer in a,b,c
 *
 */
static int max3(int a , int b , int c)
{
    return (a>b?a:b)>c?(a>b?a:b):c;
    
}

static int maxSubSum(const int A[] , int left , int right)
{
    int maxLeftSum , maxRightSum;
    int maxLeftBorderSum , maxRightBorderSum;
    int leftBorderSum , rightBorderSum;
    int center , i;
    
    if(left == right)
    {
        if(A[left] > 0)
            return A[left];
        else
            return 0;
    }
    
    center = (left + right)/2;
    maxLeftSum = maxSubSum(A, left, center);
    maxRightSum = maxSubSum(A, center+1, right);
    
    maxLeftBorderSum = 0;
    leftBorderSum = 0;
    for (i = center; i>=left; i--) {
        leftBorderSum += A[i];
        if(leftBorderSum > maxLeftBorderSum)
            maxLeftBorderSum = leftBorderSum;
    }
    
    maxRightBorderSum = 0;
    rightBorderSum = 0;
    for (i = center + 1; i<=right; i++) {
        rightBorderSum += A[i];
        if(rightBorderSum > maxRightBorderSum)
            maxRightBorderSum = rightBorderSum;
    }
    
    return max3(maxLeftSum , maxRightSum , maxLeftBorderSum + maxRightBorderSum);
    
}

int main(int argc, const char * argv[]) {
    // insert code here...
    printf("Hello, World!
");
    
    int arr[8]= {0};
    
    for(int i = 0; i <8 ; i++)
    {
        printf("type in the integer : ");
        scanf("%d",&arr[i]);
    }
    
    printf("the max sub arr sum is : %d\r",maxSubSum(arr, 0, 7));
    
    return 0;
}