动态规划――M个子串最大和 - JAVA

输入一个整数n ，表示有n个数据，输入n个数据，求出m个子串最大和；

dp[i][j] 表示与第j个数组合时，第i段子串最大和；

注意：dp[i][j] 不是前 j 个数，形成 i 段的最大和；

不经过优化的代码：

#include
  
   

using namespace std ;

#define max(x,y) ((x) > (y)   (x) : (y))
int main()	{
	int m , n ;
	cin >> m >> n ;
	int a[100] ;
	int i ;
	for( i = 1 ; i <= n ; i++ )
		cin >> a[i] ;
	int dp[100][100] = {0} ;
	for( i = 1 ; i <= m ; i++)
		for(int j = i ; j <= n ; j++)	{
			int max1 = -1000000 ;
			for(int k = i - 1 ; k < j ; k++ )
				max1 = max(max1,dp[i-1][k]) ;
			if(max1 > dp[i][j-1])
				dp[i][j] = max1 + a[j] ;
			else
				dp[i][j] = dp[i][j-1] + a[j] ;
		}
	int max2 = -1000000 ;
	for( i = 1 ; i <= n ; i++)
		max2 = max(max2,dp[m][i]) ;
	cout << max2 << endl ;
	return 0 ;
}

上面的程序时间复杂度为O(n^3) n可以取到100,0000 显然会出错，说明此程序需要简化；办什么事情都需要有一个从复杂到简单的过程，只有这样才能记得更加清晰，才能提高个人的能力……

从上面的程序中可以看出，对于每增加一个数，都要求出前一次的最大值，所以想到用一个变量来存储最大值即可解决这个问题。

#include
  
   

using namespace std ;

#define max(x,y) ((x) > (y)   (x) : (y))
int main()	{
	int m , n ;
	cin >> m >> n ;
	int a[100] ;
	int i ;
	for( i = 1 ; i <= n ; i++ )
		cin >> a[i] ;
	int dp[100][100] = {0} ;
	for( i = 1 ; i <= m ; i++)	{
		int max1 = -1000000 ;
		for(int j = i ; j <= n ; j++)	{
				max1 = max(max1,dp[i-1][j-1]) ;
			if(max1 > dp[i][j-1])
				dp[i][j] = max1 + a[j] ;
			else
				dp[i][j] = dp[i][j-1] + a[j] ;
		}
	}
	int max2 = -1000000 ;
	for( i = 1 ; i <= n ; i++)
		max2 = max(max2,dp[m][i]) ;
	cout << max2 << endl ;
	return 0 ;
}

这样稍微改动一下，就可以使程序的时间复杂度从O(n^3) 转变为 O(n^2) ，是一个很大的进步了，下一步就要对空间复杂度进行优化；

由于 dp[i][j] 的取值只与 dp[i][j-1] 和 dp[i-1][j-1] 有关，所以只用两行即可，这样直接节省了几十万倍的空间，由此可以得出：好的算法不仅仅需要得出正确的结果，更重要的是空间利用率高，速度快……

#include
  
   

using namespace std ;

#define max(x,y) ((x) > (y)   (x) : (y))
int main()	{
	int m , n ;
	cin >> m >> n ;
	int a[100] ;
	int i ;
	for( i = 1 ; i <= n ; i++ )
		cin >> a[i] ;
	int dp[2][1005] = {0} ;
	int t = 1 ;
	for( i = 1 ; i <= m ; i++)	{
		int max1 = -1000000 ;
		int t = !t ;
		for(int j = i ; j <= n ; j++)	{
				max1 = max(max1,dp[t][j-1]) ;
			if(max1 > dp[!t][j-1])
				dp[!t][j] = max1 + a[j] ;
			else
				dp[!t][j] = dp[!t][j-1] + a[j] ;
		}
	}
	int max2 = -1000000 ;
	for( i = 1 ; i <= n ; i++)
		max2 = max(max2,dp[m&1][i]) ;
	cout << max2 << endl ;
	return 0 ;
}