今年参加校招某个公司的二面时候的一个算法题

还是HR问的，题目很简单

“从一串随机的整数中，找出连续的一段，使它们的和最大”

比如有一串数字是1,-5,3,2,1,-3,2，和最大的连续的一段是3,2,1，为6

比较容易想出来的方法，就是把所有的连续的和都算出来，然后从中找个最大的

假定这串数字为a1,a2,a3…an，把第i个到第j个的和设为Sij

找出所有的Sij的时候，比较Sij的大小，最大的即为结果

不过遍历较多，对每个Sij都要遍历ai与aj之间的数

此时时间复杂度为N3

改进也很容易

知Sij=S1j-S1i，用递推的方法可以算出S1i，因为S1i=S(1i-1)+ai

扫描一次求出所有的S1i，然后再求出所有的Sij，这样，时间复杂度就降低为N2

后来回来跟同学讨论了一下，同学的算法更优，而且很聪明

因为一个负数加上一个正数一定会让正数变小，把那一列整数分段来看，分成a1,a2…ak,a(k+1)

两段数字可以相加，然后并成一段数字，这样就能求出最大的Sik，记为Smax

然后看看与a(k+1)相加的结果如何

如果是正数，则作为Smax继续往下加，前段最大的值加上这个数，构成的一定是这一段的Smax

如果是负数，则Smax=0，然后再看后面的数字相加如何，依次这样

对每次改变的Smax判断是否为最大，这样只要遍历一次，时间复杂度就变成N了

算法的优劣很明显

假如数据长度为100，第一种需要1000000的时间，第三种需要100的时间

假如数据长度为10000，第一种需要1000000000000的时间，第三种需要10000的时间

数据量越大，区别就越明显