关于“最大子数组之和”问题，如果我们只是要求得最大的和，而不需要在乎子数组的内容的话，我们可以定义一个s[n]用来存放到n为止最大的子序列和，通过s[n]=max{s[n-1]+a[n],a[n]}（a[n]用来存放输入的数组），这样再取数组s中的最大值，则是我们需要的结果。
这样的算法，我们可以很容易分析出，对于数组a我们只需要扫描一遍就可以得到所需结果，所以时间复杂度为O(n)。同样，由于只使用额外的一个一元数组，空间复杂度也是O(n)。
测试共用四组数据，结果如下
本文共 293 字，大约阅读时间需要 1 分钟。
关于“最大子数组之和”问题，如果我们只是要求得最大的和，而不需要在乎子数组的内容的话，我们可以定义一个s[n]用来存放到n为止最大的子序列和，通过s[n]=max{s[n-1]+a[n],a[n]}（a[n]用来存放输入的数组），这样再取数组s中的最大值，则是我们需要的结果。
这样的算法，我们可以很容易分析出，对于数组a我们只需要扫描一遍就可以得到所需结果，所以时间复杂度为O(n)。同样，由于只使用额外的一个一元数组，空间复杂度也是O(n)。
测试共用四组数据，结果如下
转载于:https://www.cnblogs.com/hopeful31802/p/3330295.html