服务器之家

服务器之家 > 正文

Python实现最大子序和的方法示例

时间:2021-08-01 00:58     来源/作者:神不烦

描述

给定一个序列(至少含有 1 个数),从该序列中寻找一个连续的子序列,使得子序列的和最大。
例如,给定序列 [-2,1,-3,4,-1,2,1,-5,4],
连续子序列 [4,-1,2,1] 的和最大,为 6。

我 v1.0

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
  def maxSubArray(self, nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    l = len(nums)
    i = 0
    result = nums[0]
    while i < l:
      sums = []
      temp = 0
      for j in range(i, l):
        temp+=nums[j]
        sums.append(temp)
      if result < max(sums):
        result = max(sums)
      i+=1
    return result

测试结果如下:

Python实现最大子序和的方法示例

本地运行时间为14.7s,说明我的方法太粗暴了。应该寻找更好的算法。

Python实现最大子序和的方法示例

我 优化后v1.1。优化方案,去掉sums数组,节省空间。但时间复杂度仍然不变。

?
1
2
3
4
5
6
7
8
9
10
11
l = len(nums)
  i = 0
  result = nums[0]
  while i < l:
    temp = 0
    for j in range(i, l):
      temp+=nums[j]
      if result < temp:
        result = temp
    i+=1
  return result

仍然只通过200/202测试用例,仍然超出时间限制。但本地运行时间为8.3s。有进步。

别人,分治法。时间复杂度O(NlogN)

将输入的序列分成两部分,这个时候有三种情况。
1)最大子序列在左半部分
2)最大子序列在右半部分
3)最大子序列跨越左右部分。

前两种情况通过递归求解,第三种情况可以通过。

分治法代码大概如下,emmm。。。目前还没有完全理解。

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def maxC2(ls,low,upp):
  #"divide and conquer"
  if ls is None: return 0
  elif low==upp: return ls[low]
 
  mid=(low+upp)/2 #notice: in the higher version python, “/” would get the real value
  lmax,rmax,tmp,i=0,0,0,mid
  while i>=low:
    tmp+=ls[i]
    if tmp>lmax:
      lmax=tmp
    i-=1
  tmp=0
  for k in range(mid+1,upp):
    tmp+=ls[k]
    if tmp>rmax:
      rmax=tmp
  return max3(rmax+lmax,maxC2(ls,low,mid),maxC2(ls,mid+1,upp))
 
def max3(x,y,z):
  if x>=y and x>=z:
    return x
  return max3(y,z,x)

动态规划算法,时间复杂度为O(n)。
分析:寻找最优子结构。

?
1
2
3
4
5
6
7
8
9
10
11
12
l = len(nums)
 i = 0
 sum = 0
 MaxSum = nums[0]
 while i < l:
   sum+=nums[i]
   if sum > MaxSum:
       MaxSum = sum
   if sum < 0:
     sum = 0
   i+=1
 return MaxSum

Oh!My god!!! !!!!!!!!运行只花了0.2s!!!!!!!!!!!!!!!这也太强了吧!!

Python实现最大子序和的方法示例

优化后,运行时间0.1s.

?
1
2
3
4
5
6
7
8
9
sum = 0
   MaxSum = nums[0]
   for i in range(len(nums)):
     sum += nums[i]
     if sum > MaxSum:
       MaxSum = sum
     if sum < 0:
       sum = 0
   return MaxSum

其中

sum += nums[i]必须紧挨。

?
1
MaxSum = sum

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持服务器之家。

原文链接:https://blog.csdn.net/qq_34364995/article/details/80284270

相关文章

热门资讯

2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全
2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全 2019-12-26
yue是什么意思 网络流行语yue了是什么梗
yue是什么意思 网络流行语yue了是什么梗 2020-10-11
背刺什么意思 网络词语背刺是什么梗
背刺什么意思 网络词语背刺是什么梗 2020-05-22
苹果12mini价格表官网报价 iPhone12mini全版本价格汇总
苹果12mini价格表官网报价 iPhone12mini全版本价格汇总 2020-11-13
2021德云社封箱演出完整版 2021年德云社封箱演出在线看
2021德云社封箱演出完整版 2021年德云社封箱演出在线看 2021-03-15
返回顶部