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_44321080
def 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 maxSum


if __name__ == '__main__':
  arr = [1, -2, 4, 8, -4, 7, -1, -5]
  print('1 max sub array sum:', maxSubArrSum(arr))

新闻标题:python如何求数组连续最大和的示例代码-创新互联
网站链接:http://myzitong.com/article/icoji.html