Python 최대 하위 순서 와 방법 예제

묘사 하 다.
하나의 서열(최소 1 개의 수 포함)을 지정 하고 이 서열 에서 연속 적 인 하위 서열 을 찾 아 하위 서열 과 최대 로 합 니 다.
예 를 들 어 주어진 서열[-2,1,-3,4,-1,2,1,-5,4],
연속 서브 시퀀스[4,-1,2,1]의 것 과 최대,6 이다.
나 v 1.0

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

테스트 결 과 는 다음 과 같다.
 
로 컬 운행 시간 은 14.7s 로 나의 방법 이 너무 거칠다 는 것 을 설명 한다.더 좋 은 알고리즘 을 찾 아야 한다.
 
최적화 후 v 1.1.최적화 방안,sums 배열 을 제거 하고 공간 을 절약 합 니 다.그러나 시간 복잡 도 는 변 하지 않 는 다.

  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...아직 완전히 이해 되 지 않 았 다.

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)입 니 다.
분석:최 적 화 된 서브 구 조 를 찾 습 니 다.

   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 밖 에 안 걸 렸 어!!!!!!!!!!!!!!!!!!!이 건 너무 강 한 거 아니 야!!
 
최적화 후 운행 시간 0.1s.

 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

그 속
4.567914.바짝 붙 어야 합 니 다.

MaxSum = sum

이상 이 바로 본 고의 모든 내용 입 니 다.여러분 의 학습 에 도움 이 되 고 저 희 를 많이 응원 해 주 셨 으 면 좋 겠 습 니 다.