相关知识点

C算法前缀和、前缀乘积、前缀异或的原理、源码及测试用例付视频课程

给定一个非负整数数组

时间复杂度O(nnm)n是nums的长度。

vMaxSum共有m*n种状态求每种状态需的时间复杂度是O(n)。

vPreSum记录前缀和vMaxSum[i][j]

记录将nums[0,j]分成i个子数组的最大和。

j’取值范围[0,j)vMaxSum[i][j]就是所有max(vMaxSum[i-1][j’],vPreSum[j1]

vPreSum[j’])的最小值。

这个时间复杂度在通过和不通过的边缘。

解法二滑动窗口

当jvMaxSum[i-1][j’]不变vPreSum[j1]

vPreSum[j’]

R(j,x)。

x减少后左式减少或不变右式增加或不变。

i后右式变大或不变。

所以x减少只会让右式变大或不变。

而右式显然大于左式所以减少左式不会减少最大值。

R(j,x)推论一假设一

R(j,x-1)结合假设二x-1比x更合适。

与假设一矛盾。

L(j,x-1)

R(j,x-1)]推论二对于j1,取x最大和为L(j,x)或R(j1,x);取x-1最大和为R(j1,x-1)

class

*std::max_element(nums.begin(),

nums.end());

拉伸区难度合适可以先学简单的课程请移步CSDN学院听白银讲师也就是鄙人的讲解。

https://edu.csdn.net/course/detail/38771

如何你想快

https://edu.csdn.net/lecturer/6176

相关下载

https://download.csdn.net/download/he_zhidan/88348653

鄙人想对大家说的话闻缺陷则喜是一个美好的愿望早发现问题早修改问题给老板节约钱。

墨家名称的来源有所得以墨记之。

如果程序是一条龙那算法就是他的是睛

测试环境