동적 프로그래밍의 최대 하위 배열

https://github.com/xflywind/hacking-to-the-algorithm

동적 프로그래밍은 컴퓨터 프로그래밍 최적화 방법입니다. 모든 새로운 결정은 이전의 노력을 기반으로 합니다. 따라서 이 방법은 매우 효율적입니다.

문제 설명

16개의 요소가 있는 배열이 주어지면 배열 중에서 합이 최대인 연속 요소를 찾아야 합니다.

하위 배열: [13, -3, -25] 또는 [-3, -16, -23] 또는 [18, 20, -7, 12] 등. 하위 배열의 요소는 원본 배열에서 연속적이어야 합니다.

let data = [13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7]

죽은 간단한 솔루션

완전히 간단한 해결책은 모든 하위 배열을 고려하는 것입니다. 인덱스 0부터 가능한 모든 하위 배열([13], [13, -3], [13, -3, -25], ...)을 계산합니다. 그런 다음 마지막 인덱스까지 시작 인덱스를 1씩 늘립니다.

let data = [13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7]

var maxElem = 0
for i in 0 ..< data.len:

  var value = 0
  for j in i ..< data.len:
    inc(value, data[j])
    if value > maxElem:
      maxElem = value

echo maxElem

그러나 알고리즘은 잘 확장되지 않습니다. 알고리즘의 시간 복잡도는 O(n^2)입니다.

동적 프로그래밍 솔루션

동적 프로그래밍은 양식을 채우는 것처럼 보입니다. 현재 셀은 이전 셀의 결과를 사용합니다. 이 문제를 해결하기 위해 1차원 형식을 사용합니다. 양식이 채워지면 문제가 해결됩니다.

문제를 자세히 살펴보겠습니다. 최대 하위 배열의 결과를 계산하도록 요청합니다.

먼저 원본 배열과 동일한 길이의 새 배열이 필요합니다. 그런 다음 새 배열을 채우기 시작합니다. 새 배열은 현재 최대 하위 배열의 합계를 저장합니다.

합계는 어떻게 구할 수 있습니까?

현재 합계는 원래 배열의 값에 새 배열의 최대 하위 배열에 대한 이전 합계를 더한 것과 같습니다.

먼저 원본 배열의 첫 번째 요소로 새 배열을 초기화해야 합니다. 시작 조건입니다.



그런 다음 첫 번째 셀에서 현재 셀을 계산할 수 있습니다.



따라서 최대 하위 배열은 이전 최대 하위 배열과 원래 배열의 현재 요소로 구성됩니다. 하지만 조심하세요. 원래 배열의 요소가 너무 작으면 최대 하위 배열을 얻는 데 장애가 될 수 있습니다. 즉, 이전 최대 하위 배열과 원본 배열의 현재 값을 더한 값이 0보다 작으면 현재 최대 하위 배열이 다음 최대 하위 배열에 게인을 가져올 수 없음을 의미합니다. 이 셀을 0으로 설정해야 합니다. 그러면 새 하위 배열이 다음 셀에서 시작됩니다.



최종 솔루션

proc findMaxValue*(arr: openArray[int]): int =
  ## Returns the value of maximum subarray.
  if arr.len > 0:
    var store = newSeq[int](arr.len)
    store[0] = arr[0]
    result = arr[0]

    for idx in 1 ..< arr.len:
      store[idx] = store[idx - 1] + arr[idx]

      # can't get gains
      if store[idx] < 0:
        store[idx] = 0

      # store the max value
      if store[idx] > result:
        result = store[idx]


let data = [13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7]
echo findMaxValue(data) 
# Output: 43

Source code