Python 언어를 사용하여 최대 연속 하위 시퀀스 합계를 설명합니다.

최대 연속 부분 수열의 합을 구하는 것은 매우 고전적이고 오래된 인터뷰 질문입니다. 이 기사에서는 Python 언어로 된 최대 연속 부분 수열에 대한 설명과 방법을 공유하겠습니다.

1. 문제 설명

배열(파이썬의 목록) [1,3,-3,4,-6,-1]이 있다고 가정하고 배열에서 가장 큰 연속 부분 수열의 합을 찾습니다. 예를 들어, 이 배열에서 가장 큰 연속 하위 시퀀스의 합은 5입니다. 즉, 1+3+(-3)+4 = 5

2.O(n²) 솔루션

가장 간단하고 조잡합니다. way, double 레이어 루프는 연속된 하위 시퀀스의 최대 합을 식별하기 위해 maxsum을 사용합니다. 그런 다음 각 판단이 업데이트됩니다. 할말은 별로 없고 그냥 코드로 가세요

def maxSum(list):
  maxsum = list[0]
  for i in range(len(list)):
    maxtmp = 0
    for j in range(i,len(list)):
      maxtmp += list[j]
      if maxtmp > maxsum:
        maxsum = maxtmp
  return maxsum
if __name__ == '__main__':
  list = [1,3,-3,4,-6]
  maxsum = maxSum(list)
  print "maxsum is",maxsum

실행 결과

maxsum is 5

3.O(n) 솔루션

동적인 곳이면 어디서나 솔루션을 찾을 수 있습니다. 사양은 연속된 하위 시퀀스의 최대 합에 대한 예에 대해 논의됩니다. 특히, 하위 시퀀스의 최대 연속 합은 위치 0-(n-1) 사이에서 끝나야 하기 때문에 배열이 a[i]라고 가정합니다. 그런 다음 루프가 i 번째 위치로 이동할 때 이전 연속 서브 시퀀스의 합이 0보다 작거나 같으면 위치 i에서 끝나는 연속 서브 시퀀스의 최대 합은 i 번째 위치의 값이며, 이는 a[i]입니다. 이전 연속 하위 시퀀스의 합이 0보다 큰 경우 위치 i에서 끝나는 연속 하위 시퀀스의 최대 합은 b[i] = max{ b[i-1]+a[i], a[i]}입니다. 여기서 b [i]는 가장 큰 연속 부분 수열의 합을 나타냅니다.

def maxSum(list_of_nums):
  maxsum = 0
  maxtmp = 0
  for i in range(len(list_of_nums)):
    if maxtmp <= 0:
      maxtmp = list_of_nums[i]
    else:
      maxtmp += list_of_nums[i]

    if(maxtmp > maxsum):
      maxsum = maxtmp
  return maxsum
if __name__ == &#39;__main__&#39;:
  list_of_num = [1,3,-3,4,-6]
  maxsum = maxSum(list_of_num)
  print "maxsum is: ",maxsum

Running results

maxsum is 5

위 내용은 Python 언어로 된 최대 연속 하위 시퀀스에 대한 설명과 튜토리얼입니다. 모두에게 도움이 되기를 바랍니다.

관련 권장사항:

최대 연속 하위 시퀀스 및 문제

Python의 포괄적인 숙달

간단한 팩토리 패턴의 Python 버전 소개

위 내용은 Python 언어를 사용하여 최대 연속 하위 시퀀스 합계를 설명합니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!