【アルゴリズム導論】4.1-5

最大サブ配列和の線形時間アルゴリズム

線形アルゴリズムは反復によって解く:まず以下の規定を行う:

A[i...j]A[i...j]A[i...j]は、a[i..j]a[i...j]a[i...j]a[i...j]の最も大きなサブ配列和を表す.

P[j]P[j]P[j]はa[1...j]a[1...j]a[1...j]a[1...j]にa[j]a[j]a[j]a[j]を含む最も大きなサブ配列と

を表す.
A［1…j＋1］＝m a x(A［1…j］,a［j＋1］,P［j］＋a［j＋1］,P［j］＋a［j＋1］)A［1…j＋1］＝max(A［1…j］,a［j＋1］,P［j］＋a［j＋1］,P［j］＋a［j＋1］)A［1…j＋1］＝max(A［1…j］,a［j＋1］,P［j＋1］,P［j］＋a［j＋1］,P［j］およびP［j］A［1…j］およびP［j］A［j［j］およびP［j］A［j［1…j］およびP［j］P［j］A［j］およびP［j］反復が完了するとA[1...n]A[1...n]A[1...n]A[1...n]が得られる.
コードは次のとおりです.

#define _CRT_SECURE_NO_WARNINGS
#include
void main()
{
	int n, i, j, a[3200], pre, max;
	scanf("%d",&n);
	for (i = 1; i <= n; i++)
		scanf("%d", &a[i]);
	max = pre = a[1];
	for (i = 2; i <= n; i++)
	{
		if (a[i] > max)
			max = a[i];
		if (pre + a[i] > max)
			max = pre + a[i];
		if (pre >= 0)
			pre = pre + a[i];
		else
			pre = a[i];
	}
	printf("%d
", max);
	getchar();
	getchar();
}