Home > Article > Backend Development > Use Python language to describe the maximum continuous subsequence sum
Finding the sum of the largest continuous subsequence is a very classic and old interview question. In this article, we will share with you about using Python language to describe the maximum continuous subsequence and methods, hoping to help everyone.
1. Problem description
Assume there is an array (list in python) [1,3,-3,4,-6,-1], find the largest continuous subsequence in the array of and. For example, in this array, the sum of the largest consecutive subsequences is 5, that is, 1+3+(-3)+4 = 5
2.O(n2) solution
The simplest and crudest way, double-layer loop, uses a maxsum to identify the maximum continuous subsequence sum. Then each judgment is updated. There’s not much to say, just go to the code
def maxSum(list): maxsum = list[0] for i in range(len(list)): maxtmp = 0 for j in range(i,len(list)): maxtmp += list[j] if maxtmp > maxsum: maxsum = maxtmp return maxsum if __name__ == '__main__': list = [1,3,-3,4,-6] maxsum = maxSum(list) print "maxsum is",maxsum
Running results
maxsum is 5
3.O(n) solution
Examples of finding the maximum sum of consecutive subsequences can be found anywhere where dynamic specifications are discussed. Specifically, assume that the array is a[i], because the maximum continuous sum of subsequences must end somewhere between positions 0-(n-1). Then, when the loop traverses to the i-th position, if the sum of the previous consecutive subsequences is less than or equal to 0, then the maximum sum of consecutive subsequences ending at position i is the value of the i-th position, which is a[i]. If the sum of the preceding consecutive subsequences is greater than 0, the maximum sum of consecutive subsequences ending at position i is b[i] = max{ b[i-1]+a[i], a[i]}, where b [i] refers to the sum of the largest continuous subsequence.
def maxSum(list_of_nums): maxsum = 0 maxtmp = 0 for i in range(len(list_of_nums)): if maxtmp <= 0: maxtmp = list_of_nums[i] else: maxtmp += list_of_nums[i] if(maxtmp > maxsum): maxsum = maxtmp return maxsum if __name__ == '__main__': list_of_num = [1,3,-3,4,-6] maxsum = maxSum(list_of_num) print "maxsum is: ",maxsum
Running results
maxsum is 5
The above content is described in Python language Maximum continuous subsequence and tutorial, I hope it can help everyone.
Related recommendations:
Maximal continuous subsequence and problem
Introduction to the python version of simple factory pattern
The above is the detailed content of Use Python language to describe the maximum continuous subsequence sum. For more information, please follow other related articles on the PHP Chinese website!