최대 하위 시퀀스 및 알고리즘 분석

문제 설명: n개의 정수 시퀀스 {a1, a2,...,an}이 주어지면 f(i,j)=max{0,Σa_k} 함수를 찾습니다(k: 연속 i to j);

문제는 연속된 하위 열의 합 중 최대값을 찾는 것입니다. 최대값이 음수인 경우 8개의 숫자 시퀀스 {-1, 2, -3 ,4,-2,5,-8,3}, Namo의 최대 부분 수열 합은 4+(-2)+5=7입니다.

있습니다. 이 문제의 네 가지 유형 복잡도 알고리즘, 알고리즘 1~4의 시간 복잡도는 O(n³), O(n²), O(nlogn), O(n );

알고리즘 1:

가장 직접적인 방법은 모든 상황을 나열하는 방법입니다. 하위 시퀀스의 왼쪽 끝 i와 오른쪽 끝 j를 설정한 다음 하나의 레이어를 사용할 수 있습니다. a[i ]를 a[j]의 합으로 계산합니다.

//최대 하위 열 및 전체 방법
#include
사용하여 네임스페이스 std;
int Find_Maxsun(int *a, int n);
int main(){
int n, i;
int a[100];
cin >> n;
cout for (i = 0; i cin >> i];
cout return 0;
}
int Find_Maxsun(int*a, int n){
int MaxSun = 0, i, j, k;
int NowSum;
for (i = 0; i for (j = 0; j NowSum = 0;
for (k = i; k NowSum += a[k]; /*a[i ]에서 a[j]의 하위 시퀀스까지*/
if (NowSum>MaxSun)
MaxSun = NowSum; /*업데이트 결과*/
}
return MaxSun;
}

분명히 무차별 대입 방식은 세 개의 for 루프를 사용하며 알고리즘 시간 복잡도는 O(n³)입니다. 물론 가장 어리석은 알고리즘이지만 데이터가 매우 크더라도 죽을 때까지의 리듬을 계산하려면

j가 추가될 때마다 하위 열 합계를 다시 계산해야 하는 이유를 명확하게 알 수 있습니다. j-1의 결과를 사용하지 않나요? 즉, j-1의 결과를 저장하게 되는데, j단계의 결과를 계산할 때 j-1단계를 기준으로 a[j]만 더하면 되므로 알고리즘 2가 된다.

알고리즘 2:

#include
네임스페이스 std 사용;
int Find_Maxsun2(int*a, int n);
int main(){
int n,
int a[100];
cin >> n;
cout for (i = 0; i cin >> a[i];
cout return 0;
}
int Find_Maxsun2(int*a, int n){
int i, j, NewSum = 0, MaxSum= 0;
for (i = 0; i NewSum = 0;
for (j = i; j NewSum += a[j] /*j-1 조건에서 매번 NewSum 업데이트*/
if (NewSum>MaxSum) /*Update MaxSum*/
MaxSum = NewSum;
}
}
return MaxSum;
}

이 알고리즘은 1보다 똑똑하고 알고리즘 복잡도는 O(n² ), 분명히 아직 우리가 원하는 복잡성은 아닙니다.

알고리즘 3:

알고리즘 3은 분할 및 정복이라는 아이디어를 사용합니다. 기본 아이디어는 자명합니다. 먼저 분할한 다음 정복하고, 문제를 작은 문제로 분해하고, 그런 다음 작은 문제를 요약하면 원래 시퀀스를 두 개로 나누고 가장 큰 하위 시퀀스는 왼쪽, 오른쪽 또는 경계를 가로질러 있습니다.

단계 1: 원본 시퀀스를 2개로 나누어 왼쪽 시퀀스와 오른쪽 시퀀스로 나눕니다.

2단계: 왼쪽 하위 시퀀스 S와 오른쪽 S를 재귀적으로 찾습니다.

3부: 중심선에서 양쪽으로 스캔하여 중심선과 S를 가로지르는 가장 큰 부분 수열을 찾습니다.

4단계: S=max{S left, S middle, S right} 찾기

코드는 다음과 같이 구현됩니다.

#include
네임스페이스 std 사용
int Find_MaxSum3(int*a,int low,int high);
int Max(int ​​​​a,int b,int c);
int main(){
int n, i;
int a[100];
cin >> n;
cout for (i = 0; i cin >>
cout return 0;
}
int Find_MaxSum3(int*a,int low,int high) int MaxSum = 0, MidSum, LeftSum, RightSum,i;
MidSum = 0;
if (low == high){ /*재귀 종료 조건*/
if (a[low] > 0)
return a[low];
else
return 0;
}
int mid = (low + high) / 2 //점수 중간점 찾기
LeftSum = Find_MaxSum3 (a, low, mid); /*왼쪽 시퀀스의 최대 합을 재귀적으로 구합니다*/
RightSum = Find_MaxSum3(a, mid + 1, high); right 시퀀스*/
/ *그러면 중간 경계 교차 시퀀스의 최대 합을 찾을 수 있습니다*/
int NewLeft = 0,Max_BorderLeft=0, NewRight = 0,Max_BorderRight=0;
for ( i = mid; i >= low; i- -){ /*최대 합계를 찾기 위해 왼쪽을 스캔*/
NewLeft += a[i];
if (NewLeft > Max_BorderLeft)
Max_BorderLeft = NewLeft;
}
for ( i = mid + 1; i NewRight+=a[i];
if (NewRight >= Max_BorderRight)
Max_BorderRight = NewRight;
}
MidSum = Max_BorderRight + Max_BorderLeft;
return Max(LeftSum, MidSum, RightSum); /*결과를 반환합니다. 처리*/
}
int Max(int ​​a, int b, int c){ /*3 중에서 가장 큰 수를 찾습니다*/
if ( a>= b&&a >= c)
return a;
if (b >= a&&b >= c)
return b;
if (c >= b&&c>=a)
return c;
}

알고리즘 시간 복잡도를 계산해 봅시다:

T(1)=1;

T(n)=2T(n/2)+O(n);

=2

k^T(n/2k^)+kO(n)=2k^{T(1)+kO(n) ( where n=2}k^{)=n+nlogn=O(nlogn);}

이 알고리즘은 매우 훌륭하지만 가장 빠른 알고리즘은 아닙니다.

알고리즘 4:

알고리즘 4를 온라인 처리라고 합니다. 이는 데이터 조각을 읽을 때마다 제 시간에 처리되고 얻은 결과가 현재 읽은 데이터에 대해 참임을 의미합니다. 즉, 알고리즘은 어느 위치에서나 올바른 솔루션을 제공할 수 있으며 알고리즘은 다음을 제공할 수 있습니다. 읽는 동안 올바른 해결책.

#include

사용 네임스페이스 std;
int Find_MaxSum4(int*a, int n);
int main(){
int n, i;
int a[100];
cin >> n;
cout for (i = 0; i cin >> a[i];
cout return 0;
}
int Find_MaxSum4(int*a, int n){
int i, NewSum = 0, MaxSum = 0;
for (i = 0; i NewSum += a[i]; /*현재 하위 시퀀스 합계*/
if (MaxSum MaxSum = NewSum; /*최대 하위 시퀀스 합계 업데이트*/
if (NewSum NewSum = 0;
}
return MaxSum;
}

이 알고리즘은 다음을 읽습니다. 데이터가 스캔됩니다. 동일한 문제를 해결하는 알고리즘은 매우 다릅니다. 비결은 반복 계산을 피하기 위해 컴퓨터가 몇 가지 주요 중간 결과를 기억하도록 하는 것입니다.

위의 내용은 내용의 측면을 포함하여 최대 하위 시퀀스 및 알고리즘 분석을 소개합니다. PHP 튜토리얼에 관심이 있는 친구들에게 도움이 되기를 바랍니다.