最大子数组和 最大子数组和(有长度限制) 最大m段子数组和
1.最大子数组和
可以用dp求解,只需要维护一个sum表示目前为止的最大子数组,遇到num[i]时若sum > 0则sum可以继续作为子数组更新sum为sum + num[i]否则sum更新为num[i]
2.最大子数组和(有长度限制)
135. 最大子序和 - AcWing题库
要求长度不超过m的子数组,首先求出原数组的前缀和s,这个时候考虑dp就可以得到式子dp[i] = max(s[i] - s[j])(i - m <= j < i)，因此我们需要用单调队列优化dp,我们维护一个单调队列储存数组下标使得队头元素距离i的距离小于等于m,这个单调队列是递增的因此我们要令si减去最小的sj这里的j也就是我们的队头的下标,因此我们替换队列元素的时候只要s[i]小于等于s[q[tt]]那么就弹出队尾、
3.最大m段子数组和
4546. 最大和加强加强版 - AcWing题库
一个经典的状态机模型，我们开一个dp[i][j][k]表示第i个数在第j段子数组是否被使用
若第i个数不被使用则dp[i][j][0] = max(dp[i - 1][j][0] , dp[i - 1][j][1]),之所以不考虑i - 1被划入j - 1是因为此时我们在考虑i在第j段的时候,并且此时i是不被使用的也就是说若i - 1在j - 1段而i又不被使用那么此时是不存在第j段的
若第i个数被使用则dp[i][j][1] = max(dp[i - 1][j][1](前i - 1个数凑出j段) , max(dp[i - 1][j - 1][0] , dp[i - 1][j - 1][1])这里考虑i - 1在第j段的时候之所以不考虑i - 1不被使用的情况是因为若i - 1在第j段却不被使用那么i就只能在j + 1段
因为发现每次转移只与i - 1有关因此可以用滚动数组优化空间