这是使用DP方法查找最大连续子序列和的算法。该算法似乎还可以，但是有人提到它具有空间复杂度O（n）。为什么？
在我看来，该算法具有O（1）空间复杂度。我想问的另一件事是，在不使用任何形式的递归的算法中，除了恒定的空间复杂度之外，它是否还有其他可能？
Create arrays S and T each of size n.
S[0] = A[0];
T[0] = 0;
max = S[0];
max_start = 0, max_end = 0;
For i going from 1 to n-1:
// We know that S[i] = max { S[i-1] + A[i], A[i] .
If ( S[i-1] > 0)
S[i] = S[i-1] + A[i];
T[i] = T[i-1];
Else
S[i] = A[i];
T[i] = i;
If ( S[i] > max)
max_start = T[i];
max_end = i;
max = S[i];
EndFor.
Output max_start and max_end
第一行说明了一切：
创建大小为n的数组S和T。
大小为n的数组需要Θ（n）空间，因此您的算法会自动使用Ω（n）空间。查看该算法的其余部分，您可以看到仅使用了O（1）个其他变量，并且没有递归，因此使用的总空间为Θ（n）。
通常，算法的空间复杂度取决于使用的局部变量的数量，还取决于它们的大小。数组，地图，集合，树等占用的空间与它们持有的元素数量成正比，因此，如果仅使用恒定数量的变量，则如果它们最终存储多个变量，则仍然可以使用O（1）以上的空间元素。
希望这可以帮助！
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句