연속 하위 배열 의 최대 와 문 제 를 구하 십시오.

머리말
요 며칠 동안 Weiss 의 데이터 구조 서 (Data Structures and Algorithm Analysis in C: Second Edition) 를 읽 어 왔 는데 그 중에서 두 번 째 장 은 간단 한 알고리즘 분석 (대 O기호 등 도구 도입) 에 관 한 것 으로 '연속 서브 배열 의 최대 와 문제점 을 구 하 는 것' 을 예 로 들 어 설명 과 설명 을 했다.가장 큰 하위 배열 과 문제 (원래 책 에서 '가장 큰 하위 서열 과 문제' 로 번역) 실제로 나 는 작년 여름 여름 에 집에 서 학원 OJ 를 닦 을 때 만 났 는데 나중에 가을 에 알고리즘 수업 을 하 다가 비행기 에 올 랐 을 때 도 만 났 다.인터넷 에서 이것 은 전형 적 인 면접 문 제 를 보고 Weiss 의 책 과 결합 하여 종합 적 인 토론 을 한다.
문제 설명
하나의 정수 배열 의 요 소 는 플러스 와 마이너스 가 있 습 니 다. 이 배열 에서 연속 서브 배열 을 찾 아 이 연속 서브 배열 에서 각 요소 의 최대 와 최대, 이 연속 서브 배열 은 최대 연속 서브 배열 이 라 고 부 릅 니 다.예 를 들 어 배열 {2, 4, - 7, 5, 2, - 1, 2, - 4, 3} 의 최대 연속 서브 배열 은 {5, 2, - 1, 2} 이 고 최대 연속 서브 배열 의 합 은 5 + 2 - 1 + 2 = 8 이다.문제 입력 은 하나의 배열 로 이 배열 의 '연속 서브 배열 의 최대 합' 을 출력 합 니 다.
사고 분석.
이 문제 에 대해 내 가 본 것 은 네 가지 서로 다른 시간 복잡 도의 알고리즘 이 있다.폭력 시 뮬 레이 션 은 가장 느 린 것 이 분명 하 다. 그러나 동적 계획 사상 을 응용 하면 O (N) 등급 의 선형 시간 알고리즘 을 얻 을 수 있 고 이 를 바탕 으로 약간 변형 되 어 더욱 간결 한 형식 을 얻 을 수 있다.Talk is cheap, let's show codes.
코드
해결 방법 1: 폭력 시 뮬 레이 션, 3 층 순환, O (n ^ 3) 단계

 int MaxSubsequenceSum1(const int A[],int N)  
{  
    int ThisSum=0 ,MaxSum=0,i,j,k;  
    for(i=0;i<N;i++)
        for(j=i;j<N;j++)
        {  
            ThisSum=0;  
            for(k=i;k<=j;k++)
                ThisSum+=A[k]; 
              
            if(ThisSum>MaxSum)  
                MaxSum=ThisSum;  
        }  
        return MaxSum;  
}  

 
Solution 2: Solution 1 에서 for 순환, O (N ^ 2) 단 계 를 철수 합 니 다.

int MaxSubsequenceSum2(const int A[],int N)  
{  
    int ThisSum=0,MaxSum=0,i,j,k;  
    for(i=0;i<N;i++)
    {  
        ThisSum=0;  
        for(j=i;j<N;j++)
        {  
            ThisSum+=A[j];  
            if(ThisSum>MaxSum)  
                MaxSum=ThisSum;  
        }  
    }  
    return MaxSum;  
}  

 
Solution 3: 분 치 법, 분지 경계의 처리 사고방식.
가장 큰 하위 서열 과 세 곳 에서 나타 날 수 있 기 때문에 전체 가 배열 의 왼쪽 부분 에 나타 나 거나 전체 가 오른쪽 부분 에 나타 나 거나 중간 을 넘 어 좌우 두 부분 을 차지한다.재 귀 는 좌우 하위 배열 을 두 배열 로 나 누 어 하위 배열 에 하나의 요소 만 포함 되 어 있 을 때 까지 각 층 에서 물 러 나 재 귀 하기 전에 위의 세 가지 상황 에서 최대 치 를 되 돌려 줍 니 다.
이러한 분석 에 따라 코드 를 작성 합 니 다.

 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)Base Case  
        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;  
        }  
        //      ，     
        int max1=MaxLeftSum>MaxRightSum?MaxLeftSum:MaxRightSum;  
        int max2=MaxLeftBorderSum+MaxRightBorderSum;  
        return max1>max2?max1:max2;  
}  
  

더 선명 하 게 쓰 인 다른 코드:

/*
         
*/
int Max3(int a,int b,int c)
{
    int Max = a;
    if(b > Max)
        Max = b;
    if(c > Max)
        Max = c;
    return Max;
}


int MaxSubSum2(int *arr,int left,int right)
{
    int MaxLeftSum,MaxRightSum;    //       
    int MaxLeftBorderSum,MaxRightBorderSum;    //             
    int LeftBorderSum,RightBorderSum;    //             
    int i,center;

    //          
    if(left == right)
        if(arr[left]>0)
            return arr[left];
        else
            return 0;

    //               
    center = (left + right)/2;
    MaxLeftBorderSum = 0;
    LeftBorderSum = 0;
    for(i=center;i>=left;i--)
    {
        LeftBorderSum += arr[i];
        if(LeftBorderSum > MaxLeftBorderSum)
            MaxLeftBorderSum = LeftBorderSum;
    }
    MaxRightBorderSum = 0;
    RightBorderSum = 0;
    for(i=center+1;i<=right;i++)
    {
        RightBorderSum += arr[i];
        if(RightBorderSum > MaxRightBorderSum)
            MaxRightBorderSum = RightBorderSum;
    }

    //          
    MaxLeftSum = MaxSubSum2(arr,left,center);
    MaxRightSum = MaxSubSum2(arr,center+1,right);

    //         
    return Max3(MaxLeftSum,MaxRightSum,MaxLeftBorderSum+MaxRightBorderSum);
}

/*
              
*/
int MaxSubSum2_1(int *arr,int len)
{
    return MaxSubSum2(arr,0,len-1);
}

 
이상 코드 시간 복잡 도 O (NLogN)
 
해결 방법 4: 동적 계획 (DP)
어렵 지 않 습 니 다. 이 문제 에 대해 전달 공식 은 DP [i] = max {DP [i - 1] + A [i], A [i]} 입 니 다.방정식 을 옮 긴 이상 순환 을 한 층 쓰 면 이 문 제 를 해결 할 수 있다 는 뜻 이다.
이 전이 방정식 을 이미지 로 바 꾸 는 if - else 판단, 코드 (Weiss 에서 유래 한 책) 는:

int MaxSubSum(int arr[],int len)  
{  
    int i;  
    int MaxSum = 0;  
    int ThisSum= 0;  
    for(i=0;i<len;i++)  
    {  
        ThisSum+= arr[i];  
        if(ThisSum > MaxSum)  
            MaxSum = ThisSum;  
        /*         0   ，  
                               ，  
                  0，             */
        else if(ThisSum< 0)  
            ThisSum= 0;  
    }  
    return MaxSum;  
}  

 
마지막 으로 내 가 작년 여름 방학 에 학교 OJ 문 제 를 풀 었 을 때 AC 코드 를 붙 였 다.

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
using namespace std;
int MaxsumUlt(int * arr, int size)
{
    int maxSum = 0xf0000000;
    int sum = 0;
    for(int i = 0; i < size; ++i)
    {
        if(sum < 0)
        {
            sum = arr[i];
        }
        else
        {
            sum += arr[i];
        }
        if(sum > maxSum)
        {
            maxSum = sum;
        }
    }
    return maxSum;
}

int main(){
    int n;
    while(cin>>n){
    int a[n];
    for(int i = 0;i<n;i++)
        cin>>a[i];
    printf("%d 
",MaxsumUlt(a,n));
    }

}

 
기타
Weiss 의 이 데이터 구조 책 은 정말 괜 찮 습 니 다. 제 가 학교 에서 데이터 구조 과정 을 개설 하 는 데 사용 하 는 교재 (청 화 에서 출판 한 두 권) 와 는 전혀 다 릅 니 다.다만 알고리즘 기반 이 없 는 초보 자 에 게 는 어느 정도 어려움 이 있 을 수 있 고 편폭 이 간략 하면 이해 하기 어 려 운 증가 가 있 을 수 있다.
참고 자료
　　http://blog.csdn.net/ns_code/article/details/20942045
　　http://blog.sina.com.cn/s/blog_60d6fadc0101369g.html
 
 
——————————————————————————————————————
전재 출처, AllZY 의 블 로그 원:http://www.cnblogs.com/allzy/