Back on the grid, Megumin?

咕啊咕，咕啊咕。–引言

一直在划水的Megumin终于决定要好好打打acm了。他高考失败了，他转专业失败了。要是acm再失败的话他可就只能去抡锤子搬砖了。

FeToFinal.武汉理工大学acm队19届的一个队伍，有一个数学壬，有一个没打过oi的但是现在挺厉害的妹子，还有我，oi败犬，文化课败犬，唯一一场现场赛还Fe了的我。

决定走搜索+dp，那么就刷kuangbin吧。今天先来一道dp。

原题链接：https://vjudge.net/problem/HDU-1024

题意：给出n(n<=1e6)个数，分成m个互不相交的子段，求最大的子段之和

题解：dp[i][j]保存前i段恰好分到j个数最大值，那么

dp[i][j]=max(dp[i-1][i-1->j-1]，dp[i][j-1])+a[i]

但是这里我们发现m没有给范围，而且似乎有人试过二维数组并不能开得下，于是我们可以使用滚动数组优化。

dp[j]表示前i个数分成j段的最大值。那么按照之前方程有如下核心代码：

for(int i=1;i<=m;i++)
{
	int maxx=-INF;
	for(int j=i;j<=n;j++)
	{
		dp[j]=max(dp[j-1]+a[j],maxdp[j-1]+a[j])
		//dp[j-1]即dp[i][j-1],maxx即max(dp[i-1][i-1->j-1])
		maxdp[j-1]=maxx;
		//上一次得到的dp[j-1]只能在dp[j]更新后再放进maxdp[j-1]中 
		maxx=max(maxx,dp[j]);
		//更新maxx用来进行下一次maxdp的更新 
	}
}

一个疑问：不给出m范围情况下为什么可以想O(nm)的算法啊？