분할 최소의 차분 절대 예

Question

두 서브 어레이로 배열 고려 어레이 A : I는 4 개소에서이 배열을 분할 할 수

[3, 1, 2, 4, 3] 

는 :

는

P = 1, difference = |3 − 10| = 7 
    P = 2, difference = |4 − 9| = 5 
    P = 3, difference = |6 − 7| = 1 
    P = 4, difference = |10 − 3| = 7 

최소 차이는 1

이고

배열의 각 요소는 [-1,000..1,000] 범위의 정수입니다.

아래 코드는 내가 작성한 코드입니다. 내 코드는이 연습에 적합하며 주어진 입력에 맞지만 다른 경우에는 올바르지 않습니다. 나는 왜 그런지 이해하지 못한다.

def minimaldifference(a) 
    sumArr = [] 
    sumArr = sumfromstarting(a) 
    sum = sumArr.last 
    sumRev = sumFromReverse(a, sum) 

    size = sumArr.size-2 
    min = 0 
    v = 0 
    for i in 0..size 
     if(i==0) 
      min = (sumArr[i] - sumRev[i]).abs 
     else 
      v = (sumArr[i] - sumRev[i]).abs 
      if(v < min) 
       min = v 
      end 
     end 
    end 
    min 
end 

def sumfromstarting(a) 
    sumArr = [] 
    sum = 0 
    a.each do |i| 
     sum += i 
     sumArr.push(sum) 
    end 
    sumArr 
end 

def sumFromReverse(a, sum) 
    sumArr = [] 
    rsum = 0 
    a.each do |i| 
     rsum += i 
     sumArr.push(sum - i) 
    end 
    sumArr 
end 
a = [3, 1, 2, 4, 3] 
puts minimaldifference(a) 

Answer 1

이 솔루션을 사용하려면 배열의 모든 요소가 음수가 아니어야합니다.

는

a = [4,1,3,1,2,4,3,1,5] 

있다면 다음과 같이 배열하는 것이 가능 파티션이이 테이블의 각 행

 Partition     Totals   Diff Abs Diff 
[4], [1,3,1,2,4,3,1,5]    [4, 20] 
[4,1], [3,1,2,4,3,1,5] [4+1, 20-1] =>[5, 19] -14  14 
[4,1,3], [1,2,4,3,1,5] [5+3, 19-3] =>[8, 16] -8  8 
[4,1,3,1], [2,4,3,1,5] [8+1, 16-1] =>[9, 15] -6  6 
[4,1,3,1,2], [4,3,1,5] [9+2, 15-2] =>[11, 13] -2  2 
[4,1,3,1,2,4], [3,1,5] [11+4, 13-4]=>[15, 9]  6  6 
[4,1,3,1,2,4,3], [1,5] [15+3, 9-3] =>[18, 6] 12  12 
[4,1,3,1,2,4,3,1], [5] [18+1, 6-1] =>[19, 5] 14  14 

가 "DIFF"는 두 세트의 합계 사이의 차이와 동일. a의 모든 요소는 음수가 아니므로이 값은 단조롭게 감소하지 않습니다. 따라서 절대적인 차이는 증가하지 않고 감소하지 않습니다. 합계의 최소 절대 차이를 얻으려면이 배열을 단계별로 따라 가야합니다. 다음 요소를 "오른쪽"배열에서 "왼쪽"배열로 이동하면 절대 차이가 증가 할 때 멈 춥니 다.

다음과 같이 코드에서이를 구현할 수 있습니다.

def minimize_difference(arr) 
    raise ArgumentError, "array must contain at least two elements" if arr.size < 2 
    left, *right = arr 
    last = left - right.reduce(:+) 
    left = [left] 
    while right.any? 
    test = last + 2*right.first 
    break if test.abs > last.abs 
    last = test 
    left << right.shift 
    end 
    [left, right, last.abs] 
end 

minimize_difference [3, 1, 2, 4, 3] 
    #=> [[3, 1, 2], [4, 3], 1]