최대 하위 열 과 문제 의 네 가지 해법

01 - 최대 하위 열 과 문제 (20 분) 주어진 K 개 정수 로 구 성 된 서열 {N 1, N 2,..., N K}, "연속 하위 열" 은 {N i, N i + 1,..., N j} 로 정의 되 며, 그 중 1 ≤ i ≤ j ≤ K. "최대 하위 열 과" 는 모든 연속 하위 열 요소 의 합 중 최대 자로 정의 된다. 예 를 들 어 주어진 서열 {- 2, 11, - 4, 13, - 5, - 2}연속 하위 열 {11, - 4, 13} 은 가장 큰 것 과 20 이 있 습 니 다. 프로그램 을 작성 하여 주어진 정수 서열 의 최대 하위 열 과 계산 하 라 고 요구 합 니 다. 이 문 제 는 다양한 알고리즘 이 여러 데이터 상황 에서 의 표현 을 테스트 하 는 데 목적 을 둡 니 다. 각 그룹의 테스트 데이터 특징 은 다음 과 같 습 니 다.
데이터 1: 샘플 과 등가, 테스트 기본 정확성, 데이터 2: 102 개 랜 덤 정수, 데이터 3: 103 개 랜 덤 정수, 데이터 4: 104 개 랜 덤 정수, 데이터 5: 105 개 랜 덤 정수;

int MaxSubseqSum1(int List[],int N)
{
 int i,j,k;
 int ThisSum,Maxsum=0;
 
 for(i=0;i<N;i++){
  for(j=i;j<N;j++){
   ThisSum=0;
   for(k=i;k<=j;k++)
    ThisSum+=List[k];
   if(ThisSum>MaxSum)
    MaxSum=ThisSum; 
  }
 }
 
 return MaxSum;
}

시간 복잡 도 는 nnn 방법 2:

int MaxSubseqSum1(int List[],int N)
{
 int i,j;
 int ThisSum,Maxsum=0;
 
 for(i=0;i<N;i++){
  ThisSum=0;
  for(j=i;j<N;j++){
   Thissum+=List[j];//     i，   j，  j-1    
   if(ThisSum>MaxSum)
    MaxSum=ThisSum; 
  }
 }
 
 return MaxSum;
}

시간 복잡 도 n * n
방법 3: 나 누 어 다스 린 다.

int Max(int A,int B,int C)
{
 return A>B?A>C?A:C:B>C?B:C//a>b?(a>c?a:c):(b>c?b:c)
}
int DivideAndConquer(int List[],int left,int right)
{
 int MaxLeftSum,MaxRightSum;
 int MaxLeftBorderSum,MaxRightBorderSum;
 
 int LeftBorderSum,RightBorderSum;
 int center i;
 
 if(left==right){
  if(List[left]>0)
   return List[left]
  else
   return 0;
 }
 center=(left+right)/2;
 MaxLeftSum=DivideAndConquer(List,left,center);
 MaxRightSum=DivideAndConquer(List,center+1,right);
 
 MaxLeftBorderSum=0;LeftBorderSum=0;
 for(i=center+1;i<=right;i++){
  RightBorderSum+=List[i];
  if(RightBorderSum>MaxRightBorderSum)
   MaxRightSum=RightBorderSum;
 }
 
 return Max3(MaxLeftSum,MaxRightSum,MaxLeftBorderSum+MaxRightBorderSum)
}
int MaxSubseqSum(int List[],int N)
{
 return DivideAndConquer(List,0,N-1);
}

방법 4: 온라인 처리

int MaxSubseqSum4(int List[],int N)
{
 int i;
 int ThisSum,MaxSum;
 
 ThisSum=MaxSum=0;
 for(i=0;i<N;i++)
 {
  ThisSum+=List[i];
  if(ThisSum>MaxSum)
   MaxSum=ThisSum;
  else if(ThisSum<0)
   ThisSum=0;
 }
 
 return 0;
}