1.cpp

北大judue上的题吗 供学习与交流用 大家一起分享 希望能好好学习

//最大子段和问题的错误DP解法
//d[i,j] 并不等于 max{d[i,k-1] + a[k] + d[k+1,j] | i+1 <= k <= j-1}
//其中d[i,j]表示从i到j数列中最大的子段和
#include <iostream.h>

int main()
{
	const int N = 6;
	int a[N];
	int d[N][N];
	int i , j , m , n , k , l , sum;

	for (i = 0 ; i < N ; i ++)
	{
		cin>>a[i];
	}

	for (i = 0 ; i < N ; i ++)
	{
		if(a[i] >= 0)
			d[i][i] = a[i];
		else
			d[i][i] = 0;
	}
	for (i = 0 ; i < N-1 ; i ++)
	{
		if(a[i] * a[i+1] <= 0)
			d[i][i+1] = a[i] > a[i+1] ? a[i] : a[i+1];
		else if (a[i] < 0 && a[i+1] < 0)
		{
			d[i][i+1] = 0;
		}
		else
			d[i][i+1] = a[i] + a[i+1];
	}
	for (l = 2 ; l < N ; l ++)
	{
		for (i = 0 ; i < N - l ; i ++)
		{
			j = i + l;
			d[i][j] = 0;
			for (k = i+1 ; k < j ; k ++)
			{
				sum = d[i][k-1] + d[k+1][j] + a[k];
				if (sum > d[i][j])
				{
					d[i][j] = sum;
				}
			}
		}
	}
	for (i = 0 ; i < N ; i ++)
	{
		for (j = 0 ; j < N ; j ++)
		{
			cout<<d[i][j]<<" ";
		}
		cout<<endl;
	}

	return 0;
}