题意：给一个长度为n的序列，找出m个不相交子串的和的最大值

思路：dp[i][j]表示取第j个数，并且前j个数分成i个区间的最大值，状态转移方程为 dp[i][j]=max(dp[i][j-1]+a[j], dp[i-1][k]+a[j])(k=i-1 i i+1 ... j-1 )，dp[i][j-1]+a[j]表示前j-1个分成i个区间并且取了a[j-1]，那么在a[j]取的情况下，区间数没有增加，dp[i-1][k]表示在由i-1个区间组成的答案中加入a[j]，区间数+1，这里注意一点，状态转移的时候j是从j=i开始遍历的，所以就会出现一个状态 dp[i][i-1] ,这是不可能的，要初始化为-inf，然后就是时间和空间上面的优化了，空间上面，由于每次dp状态只与上一个状态有关，所以可以用滚动数组优化，空间上对k这一维进行优化，从状态转移方程不难看出dp[i-1][k]是在找上一个状态中第二维范围为i-1到j-1的最大值，这里可以每次处理出O(1)求最大值

AC代码： 

#include "iostream"#include "iomanip"#include "string.h"#include "stack"#include "queue"#include "string"#include "vector"#include "set"#include "map"#include "algorithm"#include "stdio.h"#include "math.h"#pragma comment(linker, "/STACK:102400000,102400000")#define bug(x) cout<
     
      <<" "<<"UUUUU"<