The Python language describes the maximum sum of successive subarrays

Topic describes

HZ occasionally confuses non-computer majors with professional questions. After the test group meeting today, he spoke again: In the old one dimensional pattern recognition, it is often necessary to calculate the maximum sum of continuous subvectors, and when the vectors are all positive, the problem is easy to solve. But, if a vector contains a negative number, should it include some negative number and expect the positive next to it to make up for it? For example: {6-3-2, 7, 15,1,2,2}, the largest and continuous vector son is 8 (starting from 0, until the third). Will you be fooled by him? (The length of the subvector is at least 1)

Ideas:

The maximum and continuous subarrays 1 must have the following characteristics:

1. The first one is not negative

2. If the cumulative value of the previous number plus the current number is smaller than the current number, the cumulative value is harmful to the overall sum; If the cumulative value of the preceding number plus the current number is greater than or equal to the current number, then the cumulative value is beneficial to the overall sum.

Steps:

1. Define two variables, one for storing the previous cumulative value and one for storing the current maximum sum. Iterate over each element in the group, assuming that the i number is traversed:

(1) If the previous sum is negative or equal to 0, clear 0 and re-sum, assign the current i to the sum.

If the previous sum is an integer, then continue the sum, that is, the previous sum plus the value of the current i number as the new sum.

2. Determine whether the cumulative value is greater than the maximum: if greater than the maximum, the maximum and update; Otherwise, keep the previous maximum sum

# -*- coding: utf-8 -*- 
""" 
Date: Thu Nov 02 11:00:40 2017 
 
Created by @author: xiaoguibao 
 
E-mail: mingliumengshao@163.com 
 
 The maximum sum of consecutive subarrays  
Content:  The input 1 A plastic array, positive and negative, of the array 1 One or more in a row  
 Consisting of several integers 1 Subarray, O(n) Time maximizes the sum of all the subarrays.  
 
""" 
 
def function(lists): 
  max_sum = lists[0] 
  pre_sum = 0 
  for i in lists: 
    if pre_sum < 0: 
      pre_sum = i 
    else: 
      pre_sum += i 
    if pre_sum > max_sum: 
      max_sum = pre_sum 
  return max_sum 
 
def main(): 
  lists=[6,-3,1,-2,7,-15,1,2,2] 
  print function(lists) 
   
if __name__ == "__main__": 
  main() 

conclusion

That's the end of the Python language description of the maximum sum of consecutive subarrays, and I hope it helps. Interested friends can continue to refer to other related topics in this site, if there is any deficiency, welcome to comment out. Thank you for your support!