최 장자 단 문제 풀이

문제 설명: N 개의 정수 그룹 (A [0]... A [n - 1]) 에서 이 그룹의 하위 그룹의 최대 합 을 구하 십시오.
예:
배열: A = [1, - 2, 3, 5, - 3, 2] 복귀: 8
해법 1: 궁 거 법
모든 하위 배열 을 끝까지 들 어 각각 화 해 를 구하 고 마지막 에 최대 치 를 선택한다.
n 개 요소 의 조합 은 n * (n - 1) 가지 가 있 고 모든 조합 에 대해 c 번 이 필요 하 며 그 중에서 c 는 이 조합 요소 수 입 니 다.
따라서 이 알고리즘 의 복잡 도 는 O (n2) * O (n) = O (n3) 이다
가설 m [i, j] 는 하위 배열 (A [i]... A [j]) 을 나타 내 면 이 하위 배열 의 합 은 m [i, j - 1] + A [j] 와 같 기 때문에
m [i, j - 1] 을 알 면 m [i, j] 의 값 을 한 번 에 계산 할 수 있다.
따라서 알고리즘 을 개선 할 수 있 습 니 다. 하위 배열 의 합 을 중복 계산 하지 않도록 복잡 도 를 낮 출 수 있 습 니 다. 개선 후 T (n) = O (n2)
Python 구현:

def SubMax_force(arr):
    m = {}
    maxnum = 0
    for i inrange(len(arr)):
       m[(i,i-1)]= 0
        for j inrange(i, len(arr)):
           m[(i,j)] = m[(i,j-1)] + arr[j]
            if m[(i, j)] > maxnum:
               maxnum = m[(i, j)]
    return maxnum

 
해법 2: 분 치 법
배열 을 A [0]... A [n / 2 - 1] 과 A [n / 2]... A [n - 1] 두 부분 으로 나 누 어 각각 최대 부분 과
A [0]... A [n - 1] 의 최대 부분 과 다음 세 개의 배열 중 하나 에서 나 올 수 있 습 니 다.
1. (A[0]...A[n/2 - 1])
2. (A[n/2]...A[n-1)
3. (A [i]... A [j]) 그 중에서 i, j 는 좌우 두 개의 배열 을 뛰 어 넘 었 다.
그 중 1, 2 는 각각 재 귀적 으로 풀 수 있 고, 3 은 단독 적 으로 풀 어야 한다.
3 에 대해 서 는 A [n / 2] 로 끝 나 는 최대 부분 과 A [n / 2 + 1] 을 비롯 한 최대 부분 을 구 할 수 있 습 니 다. 그리고...
양 자 를 더 하면 된다.
이 해법 알고리즘 복잡 도 O (n * log2n)
Python 구현:

def SubMax_divide(arr):
    if len(arr)== 1:
        returnarr[0]
    sum1 =SubMax_divide(arr[0:len(arr)/2])
    sum2 =SubMax_divide(arr[len(arr)/2: len(arr)])
    sum31 =arr[len(arr)/2-1]
    sum32 =arr[len(arr)/2]
    tmp = 0
    for i inrange(len(arr)/2)[::-1]:
        tmp +=arr[i]
        if tmp> sum31:
            sum31= tmp
    tmp = 0
    for i inrange(len(arr)/2, len(arr)):
        tmp +=arr[i]
        if tmp> sum32:
            sum32= tmp
    sum3 =sum31+sum32                  
    returnmax(max(sum1,sum2),sum3)

해법 3: 동적 기획
동적 계획 의 두 가지 관건 적 인 요 소 는 '최 우수 서브 구조' 와 '중첩 서브 문제' 이다.
'최 우선 서브 구조' 는 한 문제 의 최 우선 패키지 함유 서브 문제 의 최 우선 해결 을 가리킨다
본 사례 에 대해 A [i]... A [j] 의 가장 큰 부분 과 부분 을 고려 하면 다음 과 같은 세 가지 상황 중 하나 가 될 것 이다.
1. 이 부분 은 A [i] 만 포함 합 니 다.
2. 이 부분 은 A [i] 뿐만 아니 라 이 부분 에서 A [i] 를 제외 한 부분 은 반드시 A [i + 1]... A [j] 의 A [i + 1] 을 비롯 한 가장 큰 부분 과 부분 을 가진다.
3. 이 부분 은 A [i] 를 포함 하지 않 으 면 이 부분 은 반드시 A [i + 1]... A [j] 의 가장 큰 부분 과 부분 을 가진다.
이상 의 설명 은 이 문제 가 가장 좋 은 서브 구 조 를 가지 고 있 음 을 나타 내 며 이 문 제 는 두 가지 문 제 를 포함한다.
A [i] 를 비롯 한 최대 와 자 단, Start [i] 로 기록 합 니 다.
A [i]... A [j] 의 최대 와 자 단 은 m [i, j] 로 기억 합 니 다.
이 알고리즘 은 복잡 도가 O (n) 로 두 개의 배열 로 중간 값 을 저장 합 니 다.
Python 구현:

def SubMax_dp(arr):
    Start = {}
    m = {}
    m[len(arr)-1]= Start[len(arr)-1] = arr[len(arr)-1]
    for i inrange(len(arr)-1)[::-1]:
        Start[i]= max(arr[i],Start[i+1] + arr[i])
        m[i] =max(Start[i], m[i+1])
    return m[0]

공간 최적화:
Start [i], m [i] 는 배열 의 다음 값 에 만 의존 하기 때문에 Start [i + 1], m [i + 1], 그리고 배열 이 뒤에서 앞으로 옮 겨 다 니 기 때문에 배열 을 중간 값 으로 저장 할 수 있 습 니 다.

def SubMax_dp_leSp(arr):

    m= Start = arr[len(arr)-1]
    for i in range(len(arr)-1)[::-1]:
        Start = max(arr[i],Start + arr[i])
        m = max(Start, m)
        print 'i =',i,'Start =',Start,'m =',m
    return m

프로 그래 밍 의 아름다움:
다음 알고리즘 은 이 문제 의 재 미 있 는 해법 을 보 여 주 었 습 니 다. 즉, 한 단락 에서 다른 한 끝 으로 배열 을 옮 겨 다 니 며 누적 하고 마이너스 가 되면 모든 요 소 를 버 리 고 처음부터 계산 합 니 다. 마지막 에 0 이상 의 요소 가 있 을 때 까지 계산 합 니 다.

def SubMax_beauty(arr):
    Start = arr[len(arr)-1]
    MAX = 0
    for i in range(len(arr)-1)[::-1]:
        if Start < 0:
            Start = 0
        Start += arr[i]
        if Start > MAX:
            MAX = Start
    return MAX