Home  >  Article  >  Backend Development  >  Use Python language to describe the maximum continuous subsequence sum

Use Python language to describe the maximum continuous subsequence sum

小云云
小云云Original
2017-12-06 10:42:583838browse

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__ == &#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!

Statement:
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn