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(n²) 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__ == &#39;__main__&#39;:
  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

Completely master Python

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!