알고리즘 서론 - 분할 알고리즘 최대 하위 배열 구하 기
2023 단어 알고리즘
： ， 。
：
4. 567917. 가장 직관 적 인 방법 은 바로 폭력 적 으로 해결 하 는 것 이다. 즉, 이 배열 의 모든 하위 배열 을 직접 구하 고 그 중에서 최대 치 를 선택 하 는 것 이다.그러나 폭력 법의 시간 복잡 도가 비교적 높 고 O (n ^ 2) 입 니 다. 여 기 는 코드 를 붙 이지 않 습 니 다. 마침 알고리즘 을 배 웠 기 때 문 입 니 다
4. 567917. 분 치 알고리즘 에 대한 설명: 구체 적 인 사 고 는 다음 과 같다. 한 배열 의 가장 큰 서브 배열 을 구하 고 분 치 알고리즘 을 이용 하여 먼저 해 야 할 일 은 이 배열 을 두 개의 규모 가 상당 한 서브 배열 로 나 누 는 것 이다 (왜 첫 번 째 단 계 는 이것 입 니까? 구체 적 으로 분 치 알고리즘 의 정 의 를 보 는 것 입 니 다).즉, 먼저 중간 선 mid 2 를 찾 아야 한다. 두 번 째 단 계 는 두 개의 키 배열 의 가장 큰 서브 배열 을 구 하 는 것 을 고려 해 야 한다. 그러나 다른 상황 도 나타 날 수 있다. 원래 배열 의 가장 큰 서브 배열 은 시작 위치 가 mid 왼쪽 에 있 고 종료 위 치 는 mid 오른쪽 에 있다. 즉, crossmid。 3. 그러나 어쨌든 구체 적 인 상황 은 다음 과 같은 세 가지 일 수 있다. 1. 최대 하위 그룹 은 mid 왼쪽 에 있다. 2. 최대 하위 그룹 은 mid 오른쪽 에 있다. 3. crossmid
구체 적 인 사고: 재 귀 를 사용 하 다.먼저 원수 조 를 두 개의 수조 로 나 누고 끊임없이 분할 하여 최소 (즉 low = = high) 로 구분한다.이때 의 작은 배열 의 최대 왼쪽 배열 과 최대 오른쪽 배열 및 cross 를 구하 십시오.mid. 최대 치 를 이 작은 배열 의 최대 하위 배열 로 하여 계속 재 귀 합 니 다.코드 는 다음 과 같 습 니 다.
import sys
sys.setrecursionlimit(1000000)
def max_son_array(a,low,high,mid):
left_sum=0
right_sum=0
left_max=0
right_max=0
left=mid
right=mid
for i in range(mid-1,low,-1):
left_sum+=a[i]
if left_sum>left_max :
left_max=left_sum
left=i
for i in range (mid,high):
right_sum+=a[i]
if right_sum>right_max :
right_max=right_sum
right=i
max_sum=left_max+right_max
return (max_sum , left, right)
def find_max_array(a,low,high):
if low==high:
return (low,high,a[low])
else:
mid =(low+high)//2
(l_low,l_high,l_sum)=find_max_array(a,low,mid)
(r_low,r_high,r_sum)=find_max_array(a,mid+1,high)
(c_sum,c_low,c_high)=max_son_array(a,low,high,mid)
if (l_sum>=r_sum)&(l_sum>=c_sum):
return (l_low,l_high,l_sum)
elif (c_sum>=l_sum)&(c_sum>=r_sum):
return (c_low,c_high,c_sum)
else :
return (r_low,r_high,r_sum)
aa=[13,-3,-25,20,-3,-16,-23,18,20,-7,12,-5,-22,15,-4,7]
print(find_max_array(aa,0,len(aa)-1))
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【Codility Lesson3】FrogJmpA small frog wants to get to the other side of the road. The frog is currently located at position X and wants to get to...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
