運行分而治之算法打印陣列中的最大子陣列值

Question

我已經實現了一個解決方案，以從值數組中找到最大子陣列。在運行我的分而治之算法之前，我可以打印出完整的數組，但我似乎無法弄清算法運行後如何打印子數組。

int newArray[] = {31, -41, 59, 26, -53, 58, 97, -93, -23, 84}; 

int arraySize = (sizeof(newArray)/sizeof(int)); 

printArray(newArray, 0, arraySize - 1); 

int total = maxSubDiv(newArray, 0, arraySize - 1); 

這是我主要功能的一個片段。我使用printArray函數在查找最大子數組之前打印完整數組。該maxSubDiv功能如下：

int maxSubDiv(int * Array1, int left, int right) 
{ 
    if(left == right) 
    { 
     return Array1[1]; 
    } 

    int middle = (left + right)/2; 

    return findMax(maxSubDiv(Array1, left, middle), maxSubDiv(Array1, middle + 1, right), leftRightCross(Array1, left, middle, right)); 

} 

int leftRightCross(int * Array1, int left, int middle, int right) 
{ 
    int sum = 0; 

    int leftSum = INT_MIN; 

    for(int i = middle; i >= left; i--) 
    { 
     sum = sum + Array1[i]; 
     if(sum > leftSum) 
     { 
      leftSum = sum; 
     } 
    } 

    sum = 0; 
    int rightSum = INT_MIN; 

    for(int i = middle + 1; i <= right; i++) 
    { 
     sum = sum + Array1[i]; 
     if(sum > rightSum) 
     { 
      rightSum = sum; 
     } 
    } 

    sum = leftSum + rightSum; 

    return sum; 
} 

算法似乎考好，但我只是有麻煩打印出包含最大子數組的整數子數組。任何幫助深表感謝！

struct tuple{ 

    int begin; 
    int end; 
    int length; 

}; 

int findMax(int left, int right, int cross) 
{ 

    int max; 
    if(left > right && left > cross) 
    { 
     max = left; 
    } 

    else if(right > left && right > cross) 
    { 
     max = right; 
    } 

    else 
    { 
     max = cross; 
    } 

    return(left, right, cross); 
} 

Answer 1

在maxSubDiv()當你比較的最大子陣列，而不只是長度三個子陣，回元組（開始，結束，長度）最大。 "begin","end"指定最大子數組的範圍，您可以稍後使用它來打印。您還應該從leftRightCross()返回（開始，結束，長度）。

例如，

// pesudocode 
if max is left: 
    return (left_begin, left_end, left_length) 
if max is right: 
    return (right_begin, right_end, right_length) 
if max is middle: 
    return (middle_begin, middle_end, middle_length) 

元組可以struct中實現C.