最大子数组问题 (2)

最大子数组大小一样但是几种算法的下标不一样,出现这种的问题是没有把0过滤,如在线性算法中 应该为 if (sum > 0) 而不应该为 if (sum >= 0),递归算法中的Max3比较最大子数组的问题则应该加上等号判断。还有一种是出现这种情况{1, 1, -2, 1, 1}, 这几种算法出现了两种答案[0-1]和[3-4],这个问题目前还没有解决

四种算法的时间复杂度:
$$
\begin{cases}
BruteForce & \theta(n^2) & \
DivideConquer & \theta(nlog(n)) \
BruteForce+DivideConquer & \theta(nlog(n)) \
Linear & \theta(n)
\end{cases}
$$
处理10w(为什么不是更大的数,因为暴力算法太慢了),四种算法的时间大概是

暴力算法 15.12s

简单递归算法 0.15s

优化后的递归算法 0.12s

线性算法忽略不计 0.003s

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/zzggjx.html