善变的同伴

http://www.nowcoder.com/questionTerminal/824af5cb05794606b56657bb3fa91f49

题目难度：三星
考察点：动态规划、滚动数组

方法1：动态规划

1. 分析：

这个题的本质就是就一个最大的m段字段和，本质还是动态规划。设一个dp[i][j] 表示以第j个数字结尾的前面j个数字取i段的最大和。那么对于第j个数字来说就有两种选择：
(1). 第j个数字属于最后一段，即dp[i][j] = dp[i][j-1] + a[j]
(2). 第j个数字不属于最后一段，自己是一个新段，即dp[i][j] = max{dp[i-1][k]} + a[j] 其中i-1<=k<j。
对于dp的状态转移方程就很好写了,就是(1)(2)两种选择的最大值而已，最后输出max{dp[m][i]; m<=i<=n}

算法实现：
(1). 输入相应数据
(2). 三层循环，最外层循环i从1-m表示一共有i段，第二层循环j从i到n，表示以第j个数字结尾，最内层循环就是k从i-1到j-1，为了找到max{dp[i-1][k]}，然后根据之前列出的状态转移方程。
(2). 等所有的dp[i][j]都求完之后，找到最大的max{dp[m][i]; m<=i<=n}记作ans，输出ans即可。

2. 复杂度分析：

时间复杂度：O(mn^2)
空间复杂度：O(mn)

3. 代码：

#include 
using namespace std;
const int MAXN = 1e4+5;
int a[MAXN], dp[MAXN][MAXN];
int main() {
 int n, m; cin>>n>>m;
 for(int i=1; i>a[i];
 for(int i=1; i<=m; i++) {
     for(int j=i; j<=n; j++) {
         dp[i][j] = dp[i][j-1];
         for(int k=i-1; k<j; k++) {
             dp[i][j] = max(dp[i][j], dp[i-1][k]);
         }
         dp[i][j] += a[j];
     }
 }
 int ans = 0;
 for(int i=m; i<=n; i++) ans = max(ans, dp[m][i]);
 cout<<ans<<endl;
 return 0;
}

方法2：动态规划、滚动数组优化

1.分析：

我们再来观察一下题目，我们发现题目的m和n都特别大，所以我们要想办法去掉之前的某一维，我们分析一下是可以去掉i这个维度的，由于dp[i][j]值跟dp[i-1][..]有关系，所以可以进行优化，即只用dp[j]表示以第j给数字结尾的前i个子段的最大和，接下来在来优化时间方面，其实耗费时间的内层循环时完全没有必要的，因为我们已经重复计算了很多，比如说我们在求dp[i][j]的时候，我们已经在求得了max{dp[i][j-1], max{dp[i-1][k]} }，那么我们在求dp[i][j+1]的时候就不需要在进行内层循环了，因为只需要求max{dp[i][j], dp[i-1][j]}即可，因为max{dp[i-1][k]} k<j已经求过了。所以我们只需要用一个变量sum保存一下即可，此时时间复杂度就降低为O(m*n)。

2. 复杂度分析：

时间复杂度：O(m*n)
空间复杂度：O(n)

3. 代码：

#include 
using namespace std;
const int MAXN = 1e5+5;
int a[MAXN], dp[MAXN];
int main() {
 int n, m; cin>>n>>m;
 for(int i=1; i>a[i];
 int ans = 0;
 for(int i=1; i<=m; i++) {
     int sum = 0;
     for(int j=1; j<i; j++) sum += a[j];
     ans = sum;
     for(int j=i; j<=n; j++) {
         sum = max(sum, dp[j-1])+a[j];
         dp[j-1] = ans;
         ans = max(sum, ans);
     }
     ans = max(ans, sum);
 }
 cout<<ans<<endl;
 return 0;
}

方法3：动态规划、滚动数组、预处理

1. 分析：

其实上面的方法已经能够解决大部分问题了，我们只需要做一个预处理，提前将连续的正数和连续的负数进行合并，然后在进行上述的动态规划操作，就不会超时了。

2. 复杂度分析：

时间复杂度：O(m*n)
空间复杂度：O(n)

3.代码：

#include 
using namespace std;
const int MAXN = 1e5+5;
int a[MAXN], dp[MAXN];
int main() {
 int n, m; cin>>n>>m;
 int cnt = 1;
 for(int i=1; i<=n; i++) {
     int x; cin>>x;
     if(cnt == 1) a[cnt++] = x;
     else {
         if(a[cnt-1]*x > 0) a[cnt-1] += x;
         else a[cnt++] = x;
     }
 }
 n = cnt-1;
 int ans = 0;
 for(int i=1; i<=m; i++) {
     int sum = 0;
     for(int j=1; j<i; j++) sum += a[j];
     ans = sum;
     for(int j=i; j<=n; j++) {
         sum = max(sum, dp[j-1])+a[j];
         dp[j-1] = ans;
         ans = max(sum, ans);
     }
     ans = max(ans, sum);
 }
 cout<<ans<<endl;
 return 0;
}