The Python language describes the maximum continuous subsequences and

Finding the sum of the largest continuous subsequences is a classic and very old interview question, I remember I had the same question in my job interview right after graduation. Today suddenly think of, just approaching the graduation season, and should be helpless pain of the fresh graduates of all kinds of interview time, to write a small code to solve this problem. I also hope that all comrades looking for a job will get the ideal offer in their mind. From now on, they will win the victory over Gaofu Shuai, win baifumei and walk to the peak of life.

1. Problem description

Suppose you have an array of 1 (python) [1,3,-3,4,-6,-1], and find the sum of the largest continuous subsequences in the array. For example, in this array, the sum of the maximum continuous subsequences is 5, that is, 1+3+ (-3) +4 = 5

2. O (n2) solution

The simplest approach, a double loop, USES 1 maxsum to identify the maximum continuous subsequences and. And then every time the judgment is updated. I don't have much to say about it, just code it

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

The results

maxsum is 5

3. O (n) solution

You can find examples of finding the sum of the largest continuous subsequences anywhere you talk about dynamic specifications. Specifically, assume the array is a[i], because the maximum consecutive subsequences and must end somewhere between position 0-(ES27en-1). Then, when the loop traverses to the i position, if the sum of successive subsequences preceding it is less than or equal to 0, then the maximum sum ending in position i is the value of position a[i]. If the sum of successive subsequences preceding it is greater than 0, the sum of the maximum continuous subsequences ending with position i is b[i] = max{b[ES38en-1]+a[i], a[i]}, where b[i] refers to the sum of the maximum continuous subsequences.

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

The results

maxsum is 5

conclusion

The above is the Python language description of the maximum continuous sub-sequence and all content, I hope to help you. Those who are interested can continue to see this site:

Python generates digital image code sharing

Detail of advanced filtering code for python Digital Image Processing

python+mongodb Data fetching details

If there is any deficiency, please let me know. Thank you for your support!