原题及解答
来自《小技巧求一个数组中子数组的最大和》;
题目:
输入一个整形数组,数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和。...例如输入的数组为 1, -2, 3, 10, -4, 7, 2, -5,和最大的子数组为 3, 10, -4,7, 2, 因此输出为该子数组的和 18。
...解答:
【只有子数组“前半部分”的和为正数时,子数组的求和才有可能最大】,在这个trick条件下,只需要遍历一次数组就可以。算法是:当从头开始遍历的元素的求和为正数时,继续向后遍历。...,当时经过实践和思考,这个算法同样适用于全是正数,或者全是负数的情况。...当全为正数时,最大的和自然就是所有元素的和,当全为负数时,最大和自然就是其中最大的那个负数的值。通过此算法都能得到相应的结果。