4つの解法-求子シーケンスの最大連続子シーケンスと(一般解法、求和解法、分治法、O(n)級解法)(面接経典題)

励ましは少ないコードで効率的に表現します
この4つの解法の中で、解法の1つは通法で、法則と知識を学ぶことができて、基礎の用をします;解法二解法一の基礎の上で改善を行い、思考を鍛える.解法3は有名な分治法であり、再帰的な知識に関わり、「効率的なアルゴリズム設計」の基礎となっている.解法四はO(n)の複雑さで最大連続子序和,一字,不思議を解いた.4つの解法は順序を追って漸進的で、効率は次第に向上し、精妙極まりない.初心者はどれも身につけることをお勧めします.
解法1:最も一般的な解法で、iループを定義し、配列が0からn-1の値を表し、jループを定義し、a[i]から始まり、a[j]まで終わる.kサイクルを定義し、a[i]からa[j]までのすべての数を加算し、最後に最大のサブシーケンス和を求める.時間複雑度:O(n^3)

#include
using namespace std;
int main() {
	int n; cin>>n; int a[n];
	for(int i = 0; i < n; i++) cin>>a[i];
	
	int sum = a[0];		//    0，          
	int temp = 0;
	for(int i = 0; i < n; i++)			 
		for(int j = i; j < n; j++)      //    ,  i   j   
			for(int k = i; k <=j; k++) 	//i-j      。 
				temp += a[k];  
			sum = max(sum, temp);
		}
	
	cout << sum << endl;
	return 0;
} 

解法2:数列S[n],S[i]=a[0]+a[1]+...+a[i]を定義する.j>iの場合、S[j]-S[i-1]=a[j]+a[j-1]+...+a[i]である.すなわち,2つのforループをネストし,1つはi,1つはjであり,任意のサブシーケンスの和を表すことができ,最後に比較すればよい.時間複雑度:O(n^2)

#include
using namespace std;
int main() {
	int n; cin>>n; int a[n];
	for(int i = 0; i < n; i++) cin>>a[i];
	
	int S[n+1]; S[0]=0;
	for(int i = 1; i <= n; i++) S[i] = a[i] + S[i-1];
	
	int best = 0;
	for(int i = 1; i <= n; i++) 
		for(int j = i; j <= n; j++) best = max(best, S[j]-S[i-1]);
		
return 0;}

解法三:分治法、名の通り、分して治す.
分治アルゴリズムは一般的に以下の3つのステップに分けられる:一、問題を区分する:問題の実例をサブ問題に区分する.二、再帰解:再帰的にサブ問題を解決する.三、合併問題:合併サブ問題の解は元の問題の解を得る.
最大連続和の分治アルゴリズム:1、シーケンスを要素の個数ができるだけ等しい2つの半分に分ける2、それぞれ左半分または右半分に完全に位置する最適なシーケンスを求める3、起点が左半分に位置し、終点が右半分に位置する最大連続とシーケンスを求め、サブ問題の最適解と比較する.
再帰にかかわるコードは複雑だが、本当に理解できないなら、暗記して、子供の頃覚えた古詩を考えてみると、無理に暗記しても、時間が経つにつれて、徐々に意味がわかるようになる.
時間の複雑さ:O(nlogn)(このレベルの時間の複雑さは、一般的にほとんどの競争に対処することができます)

#include
using namespace std;
int a[10005];

int longsub(int *a, int l, int r) {	//           [x,y)      
	//      a[r] ？              
	if(r-l == 1) return a[l];		//           
	int mid = l + (r-l)/2;		//     ：   [l,m) [m,r) 
	int maxs = max(longsub(a,l,mid), longsub(a,mid,r));	//     ：    
	
	int v, Lmax, Rmax;
	v=0; Lmax = a[mid-1];		//     ：  (1)——              l
	for(int i=mid-1; i>=l; i--) Lmax=max(Lmax, v+=a[i]);
	
	v=0; Rmax=a[mid];			//     ：  (2)——              r 
	for(int i=mid; i<r; i++) Rmax=max(Rmax, v+=a[i]);	 
	
	return max(maxs, Lmax+Rmax); 
}

int main() {
	int n; cin>>n;
	for(int i = 0; i < n; i++) cin>>a[i];
	cout << longsub(a, 0, n);
return 0;}

解法4:非常に特殊な解法、核心思想:i番目の要素に遍歴する時、その前の連続サブシーケンスと0より大きいかどうかを判断し、0より大きい場合、位置iで終わる最大連続サブシーケンスと要素iと前門の連続サブシーケンスと加算する.そうでなければ、位置iの最後の最大連続サブシーケンスと要素iとなる.時間複雑度:O(n)

#include
using namespace std;
int main() {
	int n; cin>>n; int a[n];
	for(int i = 0; i < n; i++) cin>>a[i];
	
	int maxsum, maxhere;
	maxsum = maxhere = a[0];	//       a[0]
	for(int i = 1; i < n; i++) {
		if(maxhere <= 0) maxhere = a[i];   //             0，         
		else maxhere += a[i]; //    ，   
		
		if(maxhere >  maxsum) maxsum = maxhere; 	//   
	} 
	cout << maxsum << endl; 
	return 0;
} 

もしこの文章があなたを助けてくれたら、ブロガーに「いいね」をあげてください.みんなのいいねは私の創作の最大の原動力です!