Use Python language to describe the maximum continuous subsequence sum

小云云
Release: 2017-12-06 10:42:58
Original
3830 people have browsed it

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
Copy after login


Running results


maxsum is 5
Copy after login
Copy after login


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
Copy after login


Running results


maxsum is 5
Copy after login
Copy after login

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!

Related labels:
source:php.cn
Statement of this Website
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
Popular Tutorials
More>
Latest Downloads
More>
Web Effects
Website Source Code
Website Materials
Front End Template
About us Disclaimer Sitemap
php.cn:Public welfare online PHP training,Help PHP learners grow quickly!