题目描述：HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢？例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。给一个数组，返回它的最大连续子序列的和，你会不会被他忽悠住？(子向量的长度至少是1)。
问题分析：
（1）首先最容易想到的就是暴力法，对于每个元素进行遍历向后求和，并对所求和依次进行比较，最后取得最大值。
代码截图：
暴力算法
暴力算法虽然简单明了，但时间复杂度为O(n²)，属实顶不住。分析一下可以看到，因为算法遍历了所有子向量，所以存在着大量重复计算。比如题目给的数组{6,-3,-2,7,-15,1,2,2},计算6-3-2+7和-3-2+7时，-3-2+7就被计算了两次。要是把这些重复计算省去，那就可以大大缩短计算时间了。
（2）可以设想，对于一个数n，若其左边的数加起来为负数，则加上n只会比n更小；只有当n左边的数和为正时，才有必要与n相加。所以只需判断一个数的左边是不是大于零，如果大于零则继续向后作和，否则从下一个元素开始重新向后计算。这种方法称为动态规划。
代码截图：
动态规划算法
网友评论