连续子数组最大和O(n）两种解法：双指针动态规划

阳光穿透心脏的1/2处 2022-04-13 14:00 128阅读 0赞

**题目描述**  
HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢？例如:\{6,-3,-2,7,-15,1,2,2\},连续子向量的最大和为8(从第0个开始,到第3个为止)。给一个数组，返回它的最大连续子序列的和，你会不会被他忽悠住？(子向量的长度至少是1)  
输入一个整形数组，求所有子数组和的最大值，要求时间复杂度为O(n)

--------------------

# 解法1 双指针+动态规划 #

采用一个指针指向最前面，一个指针指向最后面，两个指针交错移动，当移动一位发现这一位前面/后面的所有和为负数的时候，说明这两个指针夹的数组要比之前的数组和更大，如果使用递归，达不到O(N)的时间复杂度，因为有很多重复计算，因此使用两个数组来保存前向和后向遍历的和

class Solution:
        def GetSum(self, array, start, end):
            sum = 0
            for i in range(start, end + 1):
                sum += array[i]
            return sum
        def EvaluateSum(self, array, index, subArraySum, flag):
            if index == 0 or index == len(array) - 1:
                return array[index]
            else:
                if flag:
                    return subArraySum[0][index - 1] + array[index]
                else:
                    return subArraySum[1][index + 1] + array[index]
        def FindGreatestSumOfSubArray(self, array):
            # write code here
            flag = 1
            subArraySum = [([0] * len(array)) for i in range(2)]
            low, high = 0, len(array) - 1
            i = low + 1
            j = high - 1
            subArraySum[0][0] = array[0]
            subArraySum[1][len(array) - 1] = array[len(array) - 1]
            while low < high:
                if low < high and flag:
                    for i in range(low + 1, high + 1):
                        subArraySum[0][i] = self.EvaluateSum(array, i, subArraySum, flag)
                        if subArraySum[0][i - 1] < 0:
                            low = i
                            flag = 0
                            break
                elif low < high and not flag:
                    for j in range(high - 1, low - 1, -1):
                        subArraySum[1][j] = self.EvaluateSum(array, j, subArraySum, flag)
                        if subArraySum[1][j + 1] < 0:
                            high = j
                            flag = 1
                            break
                if i == high or j == low:  #跳出主循环，防止找不到更大的，low和high不改变一致循环
                    break
            return self.GetSum(array, low, high)

运行时间：25ms

占用内存：5840k

--------------------

# 解法2 用一个指针方法 #

当array\[i\]大于之前所有数字的和的时候，说明要丢弃前面所有的数组，这个时候如果array\[i\]>全局的最大值，那么需要更新全局的最大值，如果array\[i\]小于之前的和，那么判断这个和与全局最大值的大小

class Solution:
        def FindGreatestSumOfSubArray(self, array):
            # write code here
            if array == []:
                return 0
            if len(array) == 1:
                return array[0]
            maxSum = totalSum = array[0]
            #low = 0
            for i in range(1, len(array)):
                totalSum += array[i]
                print(i, array[i], totalSum, maxSum)
                if array[i] > totalSum:
                    #low = i
                    totalSum = array[i]
                    if array[i] > maxSum:
                        maxSum = array[i]
                else:
                    if totalSum > maxSum:
                        maxSum = totalSum
            return maxSum

运行时间：25ms

占用内存：5728k

--------------------

# 比较 #

两种方法时间复杂度都是O(N)，第一种解法代码量大，并且算法复杂，空间复杂度为O(2N)，因此第二种方法优