本文共 651 字，大约阅读时间需要 2 分钟。

《算法概论》习题6.1

1、定义 dp[i] 为 以S[i]作为末尾的最大连续序列的和；

2、则 dp[i] 的值只会有两种情况：

       ① dp[i] = S[i]；

       ② dp[i] = dp[i-1] + S[i]；

3、可得状态转换方程：dp[i] = max(S[i], dp[i] + S[i])。

#include 
   
    #include 
    
     using namespace std;int max(int, int);int main(){	vector
     
       S;		while (1)	{		int temp;		cin >> temp;		S.push_back(temp);		char x = getchar();		if (x == '\n')		{			break;		}	}	vector
      
        dp(int(S.size()));	dp[0] = S[0];	int maxnum = dp[0];	for (int i = 1; i < int(S.size()); ++i)	{		dp[i] = max(S[i], dp[i - 1] + S[i]);		if (maxnum < dp[i])		{			maxnum = dp[i];		}	}	cout << maxnum << endl;	return 0;}int max(int a, int b){	return a >= b ? a : b;}
      
     
    
   

转载地址：http://attai.baihongyu.com/