python如何求数组连续最大和的示例代码

题目描述：

一个有 n 个元素的数组，这 n 个元素既可以是正数也可以是负数，数组中连续的一个或多个元素可以组成一个连续的子数组，一个数组可能有多个这种连续的子数组，求子数组的最大值。例如，对于数组 [1，-2，4，8，-4，7，-1，-5] 而言，其最大和的子数组为 [4,8,-4,7]，最大值为 15。

方法：

1.蛮力法

找出所有的子数组，然后求出子数组的和，在所有子数组的和中取最大值。

代码实现：

#!/usr/bin/env python3# -*- coding: utf-8 -*-# @Time  : 2020/1/29 21:59# @Author : buu# @Software: PyCharm# @Blog  ：https://blog.csdn.net/weixin_44321080def maxSubArrSum(arr):  if arr == None or len(arr) <= 0:    print('参数不合理！')    return  thisSum = 0  maxSum = 0  i = 0  while i < len(arr):    j = i    while j < len(arr):# j 控制连续子数组包含的元素个数      thisSum = 0      k = i # k 表示连续子数组开始的下标      while k < j:        thisSum += arr[k]        k += 1      if thisSum > maxSum:        maxSum = thisSum      j += 1    i += 1  return maxSumif __name__ == '__main__':  arr = [1, -2, 4, 8, -4, 7, -1, -5]  print('1 max sub array sum:', maxSubArrSum(arr))

结果：

算法性能分析：
这种方法的时间复杂度为O(n3)；

2.重复利用已经计算的子数组和

由于 sum[i，j] = sum[i，j-1] + arr[j]，在计算 sum[i，j] 的时候可以使用前面已计算出的 sum[i，j-1] 而不需要重新计算，采用这种方法可以省去计算 sum[i，j-1] 的时间，从而提高效率。

代码实现：

#!/usr/bin/env python3# -*- coding: utf-8 -*-# @Time  : 2020/1/30 10:53# @Author : buu# @Software: PyCharm# @Blog  ：https://blog.csdn.net/weixin_44321080def maxSubArrSum(arr):  if arr == None or len(arr) <= 0:    print('参数不合理！')    return  maxSum = -2 ** 31  i = 0  while i < len(arr): # i: 0~7    sums = 0    j = i    while j < len(arr): # j: 0~7      sums += arr[j] # sums 重复利用      if sums > maxSum: # 每加一次就判断一次        maxSum = sums      j += 1    i += 1  return maxSumif __name__ == '__main__':  arr = [1, -2, 4, 8, -4, 7, -1, -5]  print('2 max sub array sum:', maxSubArrSum(arr))

结果：

算法性能分析：
使用了双重循环，时间复杂度为O(n2)；

3.动态规划

首先可以根据数组最后一个元素 arr[n-1] 与最大子数组的关系分为以下三种情况讨论：
(包含或不包含，包含的话肯定以最后一个元素结尾；不包含的话，或者最后一个元素单独构成最大子数组，或者转换为求 arr[1…n-2] 的最大子数组)