HDU 1231 最大連續子序列 DP題解

HDU 1231 最大連續子序列 DP題解

典型的DP題目，增加一個額外要求，輸出子序列的開始和結尾的數值。

增加一個記錄方法，nothing special。

記錄最終ans的時候，同時記錄開始和結尾下標；

更新當前最大值sum的時候，更新開始節點。

const int MAX_N = 10001;
long long arr[MAX_N];
int N, sta, end;

long long getMaxSubs()
{
	long long sum = 0, ans = LLONG_MIN;
	int ts = 0;
	for (int i = 0; i < N; i++)
	{
		sum += arr[i];
		if (ans < sum)
		{
			ans = sum;
			end = i;
			sta = ts;
		}
		if (sum < 0)
		{
			sum = 0;
			ts = i+1;
		}
	}
	return ans;
}

int main()
{
	while (~scanf("%d", &N) && N)
	{
		for (int i = 0; i < N; i++)
		{
			scanf("%I64d", arr+i);
		}
		long long ans = getMaxSubs();
		if (ans < 0ll)
		{
			printf("%d %I64d %I64d\n", 0, arr[0], arr[N-1]);
		}
		else
		{
			printf("%I64d %I64d %I64d\n", ans, arr[sta], arr[end]);
		}
	}
	return 0;
}

\