Максимальный SubArray с использованием Divide и Conquer

Question

Я изучаю алгоритмы из книги «Введение в алгортмс». Я хочу реализовать алгоритм разделения и покорения, чтобы найти максимальный субарифм массива. Вот мое решение, но я получаю неправильные результаты.

Любая помощь будет оценена по достоинству. Пожалуйста, объясните, так как я больше заинтересован в том, чтобы понять это больше, чем заставить его работать. Спасибо.

def maxNumber(int a, int b){ 
return a > b ? a : b; 
} 

def maxNumber(List a, List b, List c){ 
return maxNumber(a.sum(), maxNumber(b.sum(), c.sum())) 
} 

//int sum(List list){ 
// int sum = 0 
// list.each { 
//  sum+= it 
// } 
// sum 
//} 

def maxCrossing(ArrayList<Integer> list, int low, int mid, int high){ 
int sum = 0 
int leftSum = Integer.MIN_VALUE 
int maxLeftIndex = -1 

/*for (int i = low; i <= mid ; i++) { 
    sum += list[i] 
    if (sum > leftSum) { 
     leftSum = sum 
     maxLeftIndex = i 
    } 

}*/ 

for (int i = mid; i >= low ; i--) { 
    sum += list[i] 
    if (sum > leftSum) { 
     leftSum = sum 
     maxLeftIndex = i 
    } 

} 

sum = 0 
int rightSum = Integer.MIN_VALUE 
int maxRightIndex = -1 

for (int i = mid + 1; i <= high ; i++) { 
    sum += list[i] 
    if (sum > rightSum) { 
     rightSum = sum 
     maxRightIndex = i 
    } 

} 

def returnList = [] 
for (int i = maxLeftIndex; i < maxRightIndex + 1; i++) { 
    returnList.add(list[i]) 
} 
return returnList 
} 

def maxSubArray(ArrayList<Integer> list,int low, int high){ 
if (low == high) return [list[low]] 

int mid = (low + high)/2 

def leftResults = maxSubArray(list, low, mid) 
def rightResults = maxSubArray(list, mid + 1, high) 
def crossResults = maxCrossing(list, low, mid, high) 

/*if (rightResults[2] > leftResults[2] && rightResults[2] > crossResults[2]) return rightResults 
if (leftResults[2] > rightResults[2] && leftResults[2] > crossResults[2]) return leftResults 
else return crossResults*/ 


maxNumber(leftResults, rightResults, crossResults) 
} 

//Testing Features 
println("Enter array members") 
ArrayList<Integer> myList = [-2, -5, 10, -2, -3, 1, 5, -6] //System.in.newReader().readLines() 
int size = myList.size() 
def maxSum = maxSubArray(myList, 0, size - 1) 
println("Maximum sub-array is: " + maxSum) 

Answer 1

Думайте один из ваших основных проблем является отсутствие скобок вокруг своих if заявлений в maxCrossing

Итак:

if (sum > leftSum) leftSum = sum 
maxLeftIndex = i 

должно быть:

if (sum > leftSum) { 
    leftSum = sum 
    maxLeftIndex = i 
} 

Кроме того, я считают, когда ch выбирая нижнюю часть пересечения, вам нужно начинать с середины и работать вниз (может быть, здесь не так)

Кроме того, прохождение индексов и суммы не имеет большого смысла ... Я изменил его на просто возвращает максимальный массив из каждого шага (который мы можем назвать sum() на)

Вот (я думаю) рабочий раствор из кода:

def maxResults(List a, List b, List c) { 
    a.sum() > b.sum() && a.sum() > c.sum() ? a : 
    b.sum() > c.sum() ? b : 
    c 
} 

def maxCrossing(List list, int low, int mid, int high){ 
    int sum = 0 
    int leftSum = Integer.MIN_VALUE 
    int maxLeftIndex = -1 

    for (int i = mid; i >= low; i--) { 
     sum += list[i] 
     if (sum > leftSum) { 
      leftSum = sum 
      maxLeftIndex = i 
     } 
    } 

    sum = 0 
    int rightSum = Integer.MIN_VALUE 
    int maxRightIndex = -1 

    for (int i = mid + 1; i <= high ; i++) { 
     sum += list[i] 
     if (sum > rightSum) { 
      rightSum = sum 
      maxRightIndex = i 
     } 
    } 

    return list[maxLeftIndex..maxRightIndex] 
} 

def maxSubArray(List list, int low, int high){ 
    if (low == high) return [list[low]] 

    int mid = (low + high)/2 

    def leftResults = maxSubArray(list, low, mid) 
    def rightResults = maxSubArray(list, mid + 1, high) 
    def crossResults = maxCrossing(list, low, mid, high) 

    maxResults(rightResults, leftResults, crossResults) 
} 

//Testing Features 
println("Enter array members") 
ArrayList<Integer> myList = [-2, -5, 10, -2, -3, 1, 5, -6] //System.in.newReader().readLines() 
int size = myList.size() 
def maxSum = maxSubArray(myList, 0, size - 1) 
println("Maximum sub-array is: " + maxSum) 

Btw, выход из этого:

Maximum sub-array is: [10, -2, -3, 1, 5]