喜欢本站的朋友可以收藏本站,或者加入QQ群:,我们大家一起来交流技术!

我有一个关于时间复杂度（大O符号）为Java软件的问题。有没有一种方法可以快速计算或测试（或任何网站，可以计算出这对我来说将受到欢迎）。比如我想请检查是否有code下面的代码片段，并有可能提高，以及：

由于@emory指出，这可证明是不可能确定一个任意一张code自动（证明是一个的大O的时间复杂度减少从）。然而，也有可以尝试凭经验通过在几个不同的输入运行它以测量一块code的复杂工具。一个这样的工具在本文中所描述的 ，然后作品通过尝试做一个回归的程序的运行时间与它的投入规模。该工具名为 ，可在网上。

输入一个整形数组，数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。

求所有子数组的和的最大值。要求时间复杂度为O(n)。

参考博文《》，我们可以使用分治法或者减治法来处理这个问题。

目标：把1个大问题分成2个小问题，2个小问题还可以再分，直到问题规模小的可以简单解决。

将该数组等分成两个子数组，假如知道左右两侧两个数组的各自的最大子数组和，那么整个数组的最大子数组和可能为三种情况：

• 右侧数组的最大子数组和
• 左侧数组的最大子数组和
• 左右两侧数组中间毗邻位置连接形成的子数组的和的最大值（如-6，4，-3，2####5，-6，9，-8，左侧最大值为4，右侧为9，中间毗邻位置从2和5向两侧相加，得到中间毗邻子数组4，-3，2，5，-6，9和为11，三者比较得最大子数组和为11）。

递归到数组中只包含一个数字。

这种思路也是可行的。进行ln(n)次拆分，每次拆分后进行n次比较，所以算法复杂度为n*ln(n)。但还达不到题目的要求。

目标：将问题规模不断减小，直到可以简单处理为止。

假设我们已知一个数组的最大子数组和，现在在该数组后面增加一个数字，新数组的最大子数组和可能是什么呢：

• 原数组的最大子数组和；
• 新增加的数字为正数，和最右侧的子数组形成了一个新的最大子数组和（所以为了通过一次遍历完成，我们需要保存最右侧的子数组的最大和）。

然后将两个数字进行比较即可。

所以减治至数组只包含最左侧一个数字，我们知道它的最大子数组和和最右侧子数组最大和都为还数字，逐次加1个数字直到整个数组即可。

* 获得连续子数组的最大和 * 获得连续子数组的最大和 * @return 最大和，此处用了Long型是为了表示当参数为null或空时，可以返回null，返回其它任何数字都可能引起歧义。 //当右侧子数组的最大和为负数时，对于新数组，右侧子数组的最大和为新增加的数。 } else { //为正数时，对于新数组，右侧子数组的最大和为新增加的数 + 原来的最大和。 //所有子数组中最大的和
整个算法的时间复杂度为O(n)，空间复杂度为O(1).