1.1 최대 하위 열 과 문제

실례 1.1 질문   (20 분)
KK 정수 로 구 성 된 시퀀스 지정 { N_1N​1​​, N_2N​2​​, ..., N_KN​K​​ },"연속 하위 열" 은 {로 정의 되 었 습 니 다. N_iN​i​​, N_{i+1}N​i+1​​, ..., N_jN​j​​ },그 속 1 \ \ le i \ \ le j \ le K1 ≤ i ≤ j ≤ K. "최대 하위 열 과" 는 모든 연속 하위 열 요소 와 중 최대 자로 정의 된다. 예 를 들 어 주어진 서열 {- 2, 11, - 4, 13, - 5, - 2}, 그 연속 하위 열 {11, - 4, 13} 은 최대 와 20 이 있다. 정 해진 정수 서열 의 최대 하위 열 과 를 계산 하 는 프로그램 을 만들어 야 한다.
이 문 제 는 다양한 알고리즘 이 각종 데이터 상황 에서 의 표현 을 테스트 하 는 데 목적 을 둡 니 다. 각 그룹의 테스트 데이터 특징 은 다음 과 같 습 니 다.
  • 데이터 1: 샘플 과 등가, 테스트 기본 정확성;
  • 데이터 2: 102 개 무 작위 정수;
  • 데이터 3: 103 개 랜 덤 정수;
  • 데이터 4: 104 개 랜 덤 정수;
  • 데이터 5: 105 개 랜 덤 정수;
  • 입력 형식:
    첫 번 째 줄 을 입력 하여 정수 KK 를 드 립 니 다. (\ le 100000 ≤ 100000); 두 번 째 줄 은 KK 개의 정 수 를 주 고 그 사이 에 빈 칸 으로 구분한다.
    출력 형식:
    한 줄 에 최대 하위 열 을 출력 합 니 다. 시퀀스 에 있 는 모든 정수 가 마이너스 라면 0 을 출력 합 니 다.
    입력 예시:
    6
    -2 11 -4 13 -5 -2
    

    출력 예시:
    20
    #include
    #include
    int MaxSubseqSum1(int A[],int N);
    int MaxSubseqSum2(int A[],int N);
    int Max3( int A, int B, int C ); 
    int MaxSubseqSum3(int A[],int N);
    int MaxSubseqSum4(int A[],int N);
    
    int main()
    {
    	int N;
    	scanf("%d",&N);
    	int A[N];
    	int i,MaxSum1,MaxSum2,MaxSum3,MaxSum4;
        for(i=0;iMaxSum)
    			 MaxSum=ThisSum;
    		 }
    	 }
        return MaxSum;	
     } 
      int MaxSubseqSum2(int A[],int N)
     {
     	int ThisSum,MaxSum=0;
     	int i,j;
     	for(i=0;iMaxSum)
    			 MaxSum=ThisSum;
    		 }
    	 }
        return MaxSum;	
     } 
       int MaxSubseqSum4(int A[],int N)
     {
     	int ThisSum,MaxSum;
     	int i;
     	ThisSum=MaxSum=0;
     	for(i=0;iMaxSum)
     		MaxSum=ThisSum;
     		else if(ThisSum<0)
     		ThisSum=0;
    	 }
        return MaxSum;	
     }
     int Max3( int A, int B, int C )
    { /*   3         */
        return A > B ? A > C ? A : C : B > C ? B : C;
    } 
    int DivideAndConquer( int A[], int left, int right )
    { /*     List[left] List[right]       */
        int MaxLeftSum, MaxRightSum; /*           */
        int MaxLeftBorderSum, MaxRightBorderSum; /*         */
     
        int LeftBorderSum, RightBorderSum;
        int center, i;
     
        if( left == right )  { /*        ,    1    */
            if( A[left] > 0 )  return A[left];
            else return 0;
        }
     
        /*    " "    */
        center = ( left + right ) / 2; /*       */
        /*              */
        MaxLeftSum = DivideAndConquer( A, left, center );
        MaxRightSum = DivideAndConquer( 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 MaxSubseqSum3( int A[], int N )
    { /*     2           */
        return DivideAndConquer( A, 0, N-1 );
    }
    
    


    좋은 웹페이지 즐겨찾기