Maximum sum of continuous subarrays

thinking

At first, I was fooled by the title description, thinking that the sub-array must start from the zero, isn’t that easy? Start with 0, take the first and the second. Add up and look at which is the biggest and the time complexity is O (n). But this is not the case, the initial location of the subarray.Not necessarily at the beginning of the original array, and not necessarily at the end of the original array, visually speaking, is any continuous segment of the original array.

So there are several ways, the first is very crude, that is, from traversing the subarrays of element 0 to find their maximum sum, and then from these maximum sum to pick out the biggest one.

The second method is to set the initial maximum and the accumulation value, traverse the array elements, and if the accumulation value is less than 0, set the accumulation value to the elements currently traversed.

Answer

Method one is simple and crude, and the time complexity is O (n square).

class Solution:
    def FindGreatestSumOfSubArray(self, array):
        targets = []
        for i in range(len(array)):
            num = 0
            numList = []
            for j in range(i,len(array)):
                num += array[j]
                numList.append(num)
                maxNum = max(numList)
            targets.append(maxNum)
        return max(targets)

Method two, linear judgment, time complexity is O (n).

class Solution:
    def FindGreatestSumOfSubArray(self, array):
        max_sum = array[0] 
        pre_sum = 0
        for i in array: 
            if pre_sum < 0: 
                pre_sum = i 
            else: 
                pre_sum += i 
            if pre_sum > max_sum: 
                max_sum = pre_sum 
        return max_sum