还是老套路，一个角标变两个角标而已，和上题一样，暴力两重循环必挂。那么正确的解法是怎样的呢？我们接下来说这道题背后考察的要点和面试官改编的思路。

我估计不少人需要O(n^3)才做得出来，如果我告诉你，这题的最优解法是O(n)，咋一看是不是不敢相信？我们要想不去暴力解，必须要头脑冷静分析，这个子数列的一些特征。作为面试官，如果这题面试者不假思索地写答案，如果还写对了，十有***是背答案，依然是不给过。

如果，我们确定了数组中的某一个元素作为子数列的元素，那么我们该如何找最大的子数列？我们不妨把问题简化一下：如果，我们确定了数组中的某一个元素作为子数列的最末位数，那么我们该如何找最大的子数列？这时候，我们往前看一位，如果以A[i-1]作为尾数的子数列，加起来全是负值，那么这个以A[i]为尾数的最大子数列就是{A[i]}，只有自身一个元素；反之，如果和是正数，则是A[i-1]为尾数的子数列，拼上A[i]。那么以此类推，在一轮循环中，我们找到以A[i]为终点的子数列最大和，一轮循环过后，就得到我们的答案了。

举例：[−1, 1, −3, 4, −1, 2, 1, −5, 8]，以第一个数为终点，最大的子数列就是自己，最大和为-1，第二个数，因为arr[1]的前一个数arr[0]为终点的子数列是负数，所以以arr[1]为终点，最大子数列就是自己，和就是1，以此类推，直到最后一位。