0

値の配列から最大の部分配列を見つけるソリューションを実装しました。分割統治アルゴリズムを実行する前に完全な配列を出力できますが、アルゴリズムの実行後に部分配列を出力する方法がわかりません。

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);
}
4

1 に答える 1

0

3maxSubDiv()つの部分配列の最大値を比較する場合、長さだけでなく、最大部分配列のタプル (開始、終了、長さ) を返します。"begin"、"end"最大部分配列の範囲を指定します。これは、後で印刷に利用できます。また、(begin, end, length) from を返す必要があります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で実装できます。

于 2015-10-15T04:19:10.860 に答える