【hdoj_1003】Max Sum

題目連結：http://acm.hdu.edu.cn/showproblem.php?pid=1003

題目大意，給定一個數組，a[0], a[1], ..., a[n-1]需要求它的一個連續子序列，使得這個連續子序列的和最大.

一、暴力求解方法O(n^3)

直覺的解法是，周遊所有的連續子序列，取和最大的那個.唯一決定一個連續子序列的名額為序列起始、結束索引，分别設定為i和j則，要求a[i],...,a[j]的和.其中0<=i<n, i<=j<n，如此周遊即可.i和j為兩層循環，求和一層循環，共三層循環，複雜度O(n^3)，代碼如下：

#include <iostream>
using namespace std;

int main()
{
	int T;
	cin >> T;
	while(T--)
	{
		int n, i, j, k;
		cin >> n;
		int *a = new int[n];
		for(i=0;i<n;i++)
			cin >> a[i];
		int maxsum = -9999999;
		int start = 0, end = 0;

		for(i=0;i<n;i++)	//Time complexity: O(n^3)
		{
			for(j=i;j<n;j++)	// pay attention this: j starts from i not i+1
			{	
				int sum = 0;
				for(k=i;k<=j;k++)
				{
					sum += a[k];
				}
				if(sum>maxsum)
				{
					maxsum = sum;
					start = i;
					end = j;
				}
			}

		}
		cout << maxsum << " " << start+1 << " " << end+1 << endl;

		delete [] a;
	}
	
	return 0;
}
           

二、暴力求解方法O(n^2)

比方法一複雜度低的暴力求解方法，主要技巧是：先求出從a[0]開始到a[i]的和S_i(0<=i<n)，一次循環. 再計算S_i+1,j = S_j - S_i, 注意下表的範圍.由于不用求和，隻需要計算兩個值的內插補點，是以隻有i和j循環，兩層，複雜度O(n^2).

需要注意下标的問題.代碼如下：

#include<iostream>
using namespace std;

int main()
{
	int T;
	cin >> T;
	while(T--)
	{
		int n, i, j;
		cin >> n;
		int *a = new int[n+1];	//pay attention the index: S_i+1,j = S_j - S_i
		int *sum0_i = new int[n+1];

		for(i=1;i<=n;i++)
		{
			cin >> a[i];
			sum0_i[i] = 0;
		}
		sum0_i[0] = 0;
		for(i=1;i<=n;i++)
			sum0_i[i] = sum0_i[i-1] + a[i];
		int maxsum = -99999;
		int start, end;
		for(i=0;i<=n;i++)
		{
			for(j=i+1;j<=n;j++)
			{
				int d = sum0_i[j]-sum0_i[i];
				if(d > maxsum)
				{
					maxsum = d;
					start = i+1;	// start = i+1 not i !!
					end = j;
				}
			}
		}

		cout << maxsum << " " << start << " " << end << endl;

		delete []a;
	}

	return 0;
}
           

三、暴力求解方法O(n^2)

思路和二差不多，主要省去了求和這一層，技巧是：利用前面求和的結果，而不是重新循環一次.代碼如下：

#include<iostream>
using namespace std;

int main()
{
	int T;
	cin >> T;
	while(T--)
	{
		int n, i, j;
		cin >> n;
		int *a = new int[n];
		for(i=0;i<n;i++)	cin >> a[i];

		int maxsum = -99999;
		int start=0, end=0;
		for(i=0;i<n;i++)	// Time complexity: O(n^2)
		{
			int sum = 0;
			for(j=i;j<n;j++)
			{
				sum += a[j];
				if(sum>maxsum)
				{
					maxsum = sum;
					start = i;
					end = j;
				}
			}
		}

		cout << maxsum << " " << start+1 << " " << end+1 << endl;

		delete []a;
	}

	return 0;
}
           

四、分治法O(nlogn)

不懂

五、累積求和的方法

這種方法最重要的一點是：

給定數組，a[0], a[1], ..., a[i], ...,a[j], ..., a[n-1]，設S[i,j] = a[i]+a[i+1]+...+a[j]

如果S[i, j]<0, 那麼S[i, j] + a[j+1] < a[j+1]， 是以連續子序列{a[i], ..., a[j], a[j+1]}這個子序列的和一定是最大的，是以子序列{a[i], ..., a[j]}沒有繼續增長的必要，需要從a[j+1]開重新增長子序列

(上面僅供思考，不是嚴謹的證明)

AC的代碼如下：

#include<iostream>
using namespace std;

int main()
{
	int T;
	cin >> T;
	int t = 0;
	while(T--)
	{
		t ++;
		int n, i, j;
		cin >> n;
		int *a = new int[n];
		for(i=0;i<n;i++)
			cin >> a[i];
		int maxsum = -9999;
		int sum = 0;
		int startMax = 0, endMax = -1;
		int startTemp = 0, endTemp = -1;
		for(i=0;i<n;i++)
		{
			sum+=a[i];
			endTemp ++;
			if(sum>maxsum)
			{
				maxsum = sum;
				startMax = startTemp;
				endMax = endTemp;
			}
			if(sum<0)
			{
				sum = 0;
				startTemp = i+1;
				endTemp = i;
			}
		}

		cout << "Case " << t << ":" << endl;
		cout << maxsum << " " << startMax+1 << " " << endMax+1 << endl;
		if(T>0)
			cout << endl;

		delete []a;
	}

	return 0;
}
           

詳細的解答參考：

最大連續子序列和：動态規劃經典題目(2)