易保研機試験訓練キャンプ-基礎キャンプ|動的計画|C-最大連続サブシーケンス

に言及
K個の整数のシーケンス{N 1,N 2,...,NK}が与えられ、その任意の連続サブシーケンスは{Ni,Ni+1,...,Nj}として表すことができ、そのうち1<=i<=j<=Kである.最大連続サブシーケンスは、すべての連続サブシーケンスの要素と最大の1つであり、例えば、所与のシーケンス{−2,11,−4,13,−5,−2}であり、その最大連続サブシーケンスは{11,−4,13}、最大および20である.今年のデータ構造の答案用紙では、プログラムの作成に最大和を要求し、サブシーケンスの最初の要素と最後の要素を出力する必要があるという要求が追加されました.
Input
テスト入力にはいくつかのテスト例が含まれており、各テスト例は2行を占め、1行目は正の整数K(<10000)を与え、2行目はK個の整数を与え、中間はスペースで区切られている.Kが0の場合、入力は終了し、この例は処理されない.
Output
各テスト例について、最大および最大連続サブシーケンスの最初の要素と最後の要素を1行に出力し、中間をスペースで区切ります.最大連続サブシーケンスが一意でない場合、出力シーケンス番号iおよびjが最小である(例えば、入力サンプルの2番目、3番目のグループ).すべてのK個の要素が負数である場合、最大と0を定義し、シーケンス全体の先頭と末尾の要素を出力します.
Sample Input
6 -2 11 -4 13 -5 -2 10 -10 1 2 3 4 -5 -23 3 7 -21 6 5 -8 3 2 5 0 1 10 3 -1 -5 -2 3 -1 0 -2 0
Sample Output
20 11 13 10 1 4 10 3 5 10 10 10 0 -1 -2 0 0 0
hint
Huge input, scanf is recommended.
タイムアウトコード

#include 
#include 
using namespace std;
struct info{
	int begin;
	//     
	int sum; 
};
int main() {
	int g[10000];
	info h[10000];
	int k;
	bool flag = false;
	while(cin >> k) {
		flag = false;
		if(k == 0)
			break;
		for(int i = 1; i <= k; ++i) {
			cin >> g[i];
			if(g[i] >= 0) flag = true;
			h[i].begin = i;
			h[i].sum = g[i];
			int s = h[i].sum;
			for(int j = i - 1; j >= 1; --j) {
				s += g[j];
				if(s > h[i].sum) {
					h[i].sum = s;
					h[i].begin = j;
				}
			}
		}
		info M;
		M.sum = h[1].sum;
		M.begin = h[1].begin;
		int end = 1;
		for(int i = 2; i <= k; ++i) {
			if(h[i].sum > M.sum) {
				M.sum = h[i].sum;
				M.begin = h[i].begin;
				end = i;
			}
		}
		if(flag == false)
			cout << 0 << ' ' << g[1] << ' ' << g[k] << endl;
		else {
			cout << M.sum << ' ' << g[M.begin] << ' ' << g[end] << endl;
		}
	}
	return 0;
} 

正しいコード

#include 
using namespace std;
int main() {
	int g[10000];
	int k;
	bool flag = false;
	while(cin >> k) {
		flag = false;
		if(k == 0)
			break;
		for(int i = 1; i <= k; ++i) {
			cin >> g[i];
			if(g[i] >= 0) flag = true;
		}
		if(flag == false) {
			cout << 0 << ' ' << g[1] << ' ' << g[k] << endl;
			continue;
		}
		int MAX = g[1];
		int sum = g[1];
		int begin = 1;
		int end = 1;
		int temp = 1;
		for(int i = 2; i <= k; ++i) {
			if(sum < 0) {
				sum = 0;
				temp = i;
			}
			sum += g[i];
			if(sum > MAX) {
				MAX = sum;
				end = i;
				begin = temp;
			}
		}
		cout << MAX << ' ' << g[begin] << ' ' << g[end] << endl;
	}
	return 0;
}