데이터 구조 면접 문제 요약 7 - 배열: 최대 연속 서브 세그먼트 와 최대 연속 서브 세그먼트 축적

우 리 는 먼저 최대 연속 부분 과
문제 설명: 배열 (요 소 는 마이너스, 출력 배열 의 모든 연속 하위 배열 의 최대 값 을 지정 합 니 다.
이 문 제 는 여러 가지 해법 이 있다.
첫 번 째: 순환 끼 워 넣 기, 모든 조합 을 찾 아 최대 치 를 기록 합 니 다. 시간 복잡 도 O (n ^ 2).

int MaxSum(int *v,int n,int *besti,int *bestj)
{
    int sum=0;
    int i,j;
    for (i=1;i<=n;i++)
    {
        int thissum=0;
        for (j=i;j<=n;j++)
        {
            thissum+=v[j];
            if (thissum>sum)
            {
                sum=thissum;
                *besti=i;
                *bestj=j;
            }
        }
    }
    return sum;
}

두 번 째 방법 은 귀속 이다.
초기 문 제 는 n 크기 의 배열 을 처리 해 야 하기 때문에 이 를 두 개의 배열 a 와 b 로 나 눈 다음 에 a, b 에서 요소 의 총화 가 가장 큰 하위 배열 을 각각 MaxA, MaxB 로 나 눌 수 있 습 니 다. 가장 큰 하위 배열 은 a 에서 나 누 거나 b 에서 나 누 거나 a 와 b 사이 의 경 계 를 뛰 어 넘 거나 우 리 는 경 계 를 뛰 어 넘 는 가장 큰 하위 배열 을 MaxC 로 기록 할 것 입 니 다. 우 리 는 분할 알고리즘 계산 처 를 통 해 계산 할 것 입 니 다.MaxA 와 MaxB 를 통 해 어떤 방법 으로 MaxC 를 계산 한 다음 에 세 개의 가장 큰 값 을 되 돌려 주 는 것 이 우리 가 원 하 는 가장 큰 하위 배열 과.

int MaxSum_DIV(int *v,int l,int r)
{
    int k,sum=0;
    if(l==r)
        return v[l]>=0?v[l]:0;
    else
    {
        int center=(l+r)/2;

//    
        int lsum=MaxSum_DIV(v,l,center);

//    
        int rsum=MaxSum_DIV(v,center+1,r);
//      
        int s1=0;
        int lefts=0;
        for (k=center;k>=l;k--)
        {
            lefts+=v[k];
            if(lefts>s1)
                s1=lefts;
        }

        int s2=0;
        int rights=0;
        for (k=center+1;k<=r;k++)
        {
            rights+=v[k];
            if(rights>s2)
                s2=rights;
        }
        sum=s1+s2;
        if(sum

시간 복잡 도 T (n) = 2 * T (n / 2) + O (n), 최종 T (n) = O (nlogn) 를 분석 해 보 겠 습 니 다.
인터넷 에 또 하나의 코드 가 있다.

int maxsum3(int *array,const int begin,const int end)
{
    int mid = 0;
    int lmax=0,rmax =0;
    int tempsum = 0;
    if(begin==end)
        return array[begin];
    mid = (begin+end) / 2;
    for(int i=mid;i>=begin;--i)
    {
        tempsum += array[i];
        lmax = max(lmax,tempsum);
    }
    tempsum = 0;
    for(int j=mid+1;j<=end;++j)
    {
        tempsum += array[j];
        rmax = max(rmax,tempsum);
    }
    return max(lmax+rmax,maxsum3(array,begin,mid),maxsum3(array,mid+1,end));
}

이 두 단락 의 재 귀 는 그다지 이해 하기 어 려 운 것 이 아니다. 특히 재 귀 를 자주 쓰 지 않 는 친구 들 에 게 기회 가 있 으 면 나 는 재 귀 를 전문 적 으로 이야기 하 는 글 을 한 편 더 쓸 것 이다.
세 번 째 방법 입 니 다. 물론 우 리 는 더 좋 은 해법 이 있 습 니 다. 그것 은 바로 동적 계획 입 니 다. 먼저 우리 가 가장 큰 부분 과 시, 부분 과 특징 을 분석 해 보 겠 습 니 다. 만약 앞의 부분 과 0 보다 크 면 우 리 는 다음 요 소 를 계속 추가 합 니 다. 만약 부분 과 0 보다 작다 면 우 리 는 이전의 모든 요 소 를 포기 하고 다시 부분 을 찾 습 니 다. 물론 전에 만 났 던 부분 을 찾 습 니 다.세그먼트 와 최대 값 을 기록 합 니 다. 이 과정 은 동적 계획 의 과정 입 니 다. 이러한 시간 복잡 도 는 세 가지 방법 중에서 도 가장 작은 O (n) 입 니 다.

int MaxSum_DYN(int *v,int n)
{
    int sum=0,b=0;
    int i;
    for (i=1;i<=n;i++)
    {

//       
        if(b>0)
            b+=v[i];
        else
            b=v[i];

//       
        if(b>sum)
            sum=b;
    }
    return sum;
}

이상 의 내용 은 감사 해 야 합 니 다.
http://www.cnblogs.com/Anker/archive/2013/03/03/2941959.html
http://www.cnblogs.com/hustcat/archive/2009/06/01/1493949.html
나 는 단지 그들의 코드 에 대해 조금 만 설명 할 뿐, 코드 는 가능 한 한 바 꾸 지 않 았 다. 그래서 이 게시 물 은 내 가 종합 한 것 이지, 결코 완전히 오리지널 이 아니다.
가장 큰 부분 과 문 제 를 해결 한 후에 많은 학우 들 이 가장 큰 부분 적 인 문 제 를 해결 할 것 이다.
앞의 두 가지 방법 이 가장 좋 은 것 은 아니다. 우 리 는 면접 에서 문 제 를 푸 는 과정 에서 사용 하지 않 는 것 이 가장 좋다. 우 리 는 동태 계획 의 방법 만 본다.
우 리 는 가장 큰 부분 적 을 찾 는 과정 에서 앞의 부분 적 이 1 보다 크 면 되 고 1 보다 작은 부분 은 모두 포기 합 니 다.

int MaxMulti(int *v,int n)
{
    int mul=0,b=0;
    int i;
    for (i=1;i<=n;i++)
    {
//       
        if(b>1)
            b*=v[i];
        else
            b=v[i];
//       
        if(b>mul)
            mul=b;
    }
    return mul;
}