Revisions to Find the contiguous subarray within an array (containing at least one number) which has the largest sum

edited body

Source Link

edited May 2, 2016 at 5:12

32.1k
15
78
205

#include <stdio.h>
#define MAX(a, b) (a) > (b) ? (a) : (b)

int maxSubArray(const int* A, int n1)
{
    int currIndex     = 0;
    int maxSumTillNow = A[0];
    int maxSumStart   = 0;
    int maxSumLength  = 1;
    int currLength;
    int sum;
    int firstNeg;

    while (currIndex <= n1 - 1)
    {
        if(A[currIndex] < 0)
        {
            if(A[currIndex] > maxSumTillNow)
            {
                maxSumTillNow = A[currIndex];
            }

            currIndex++;
            continue;
        }

        sum = 0;
        firstNeg = -1;

        for (currLength = 0; currLength + currIndex <= n1 - 1; currLength++)
        {
            sum += A[currIndex+currLength];

            if (sum > maxSumTillNow)
            {
                maxSumTillNow = sum;
                maxSumStart   = currIndex;
                maxSumLength  = currLength + 1;
            }

            if (firstNeg == -1 && A[currIndex + currLength] < 0)
            {
                firstNeg = currIndex+currLength;
            }
        }

        if(firstNeg == -1)
        {
            break ;
        }

        currIndex = firstNeg + 1;
    }

    return maxSumTillNow;
}

int kadanesAlgorithm(const int* array, const size_t length)
{
    int maximum_so_far = array[0];
    int maximum_end    = array[0];

    for (size_t index = 1; index < length; ++index)
    {
        const int x    = array[index];
        maximum_end    = MAX(maximum_end + x, 0x);
        maximum_so_far = MAX(maximum_end, maximum_so_far);
    }

    return maximum_so_far;
}

int main(int argc, const char * argv[]) {
    int arr[] = { -2, 1, -3, 4, -1, 2, 1, -5, 4 };
    printf("Original result: %d\n", maxSubArray(arr, 9));
    printf("Kadane's result: %d\n", kadanesAlgorithm(arr, 9));
}

#include <stdio.h>
#define MAX(a, b) (a) > (b) ? (a) : (b)

int maxSubArray(const int* A, int n1)
{
    int currIndex     = 0;
    int maxSumTillNow = A[0];
    int maxSumStart   = 0;
    int maxSumLength  = 1;
    int currLength;
    int sum;
    int firstNeg;

    while (currIndex <= n1 - 1)
    {
        if(A[currIndex] < 0)
        {
            if(A[currIndex] > maxSumTillNow)
            {
                maxSumTillNow = A[currIndex];
            }

            currIndex++;
            continue;
        }

        sum = 0;
        firstNeg = -1;

        for (currLength = 0; currLength + currIndex <= n1 - 1; currLength++)
        {
            sum += A[currIndex+currLength];

            if (sum > maxSumTillNow)
            {
                maxSumTillNow = sum;
                maxSumStart   = currIndex;
                maxSumLength  = currLength + 1;
            }

            if (firstNeg == -1 && A[currIndex + currLength] < 0)
            {
                firstNeg = currIndex+currLength;
            }
        }

        if(firstNeg == -1)
        {
            break ;
        }

        currIndex = firstNeg + 1;
    }

    return maxSumTillNow;
}

int kadanesAlgorithm(const int* array, const size_t length)
{
    int maximum_so_far = array[0];
    int maximum_end    = array[0];

    for (size_t index = 1; index < length; ++index)
    {
        const int x    = array[index];
        maximum_end    = MAX(maximum_end + x, 0);
        maximum_so_far = MAX(maximum_end, maximum_so_far);
    }

    return maximum_so_far;
}

int main(int argc, const char * argv[]) {
    int arr[] = { -2, 1, -3, 4, -1, 2, 1, -5, 4 };
    printf("Original result: %d\n", maxSubArray(arr, 9));
    printf("Kadane's result: %d\n", kadanesAlgorithm(arr, 9));
}

#include <stdio.h>
#define MAX(a, b) (a) > (b) ? (a) : (b)

int maxSubArray(const int* A, int n1)
{
    int currIndex     = 0;
    int maxSumTillNow = A[0];
    int maxSumStart   = 0;
    int maxSumLength  = 1;
    int currLength;
    int sum;
    int firstNeg;

    while (currIndex <= n1 - 1)
    {
        if(A[currIndex] < 0)
        {
            if(A[currIndex] > maxSumTillNow)
            {
                maxSumTillNow = A[currIndex];
            }

            currIndex++;
            continue;
        }

        sum = 0;
        firstNeg = -1;

        for (currLength = 0; currLength + currIndex <= n1 - 1; currLength++)
        {
            sum += A[currIndex+currLength];

            if (sum > maxSumTillNow)
            {
                maxSumTillNow = sum;
                maxSumStart   = currIndex;
                maxSumLength  = currLength + 1;
            }

            if (firstNeg == -1 && A[currIndex + currLength] < 0)
            {
                firstNeg = currIndex+currLength;
            }
        }

        if(firstNeg == -1)
        {
            break ;
        }

        currIndex = firstNeg + 1;
    }

    return maxSumTillNow;
}

int kadanesAlgorithm(const int* array, const size_t length)
{
    int maximum_so_far = array[0];
    int maximum_end    = array[0];

    for (size_t index = 1; index < length; ++index)
    {
        const int x    = array[index];
        maximum_end    = MAX(maximum_end + x, x);
        maximum_so_far = MAX(maximum_end, maximum_so_far);
    }

    return maximum_so_far;
}

int main(int argc, const char * argv[]) {
    int arr[] = { -2, 1, -3, 4, -1, 2, 1, -5, 4 };
    printf("Original result: %d\n", maxSubArray(arr, 9));
    printf("Kadane's result: %d\n", kadanesAlgorithm(arr, 9));
}

edited body

Source Link

edited May 1, 2016 at 18:48

coderodde

32.1k
15
78
205

#include <stdio.h>
#define MAX(a, b) (a) > (b) ? (a) : (b)

int maxSubArray(const int* A, int n1)
{
    int currIndex     = 0;
    int maxSumTillNow = A[0];
    int maxSumStart   = 0;
    int maxSumLength  = 1;
    int currLength;
    int sum;
    int firstNeg;

    while (currIndex <= n1 - 1)
    {
        if(A[currIndex] < 0)
        {
            if(A[currIndex] > maxSumTillNow)
            {
                maxSumTillNow = A[currIndex];
            }

            currIndex++;
            continue;
        }

        sum = 0;
        firstNeg = -1;

        for (currLength = 0; currLength + currIndex <= n1 - 1; currLength++)
        {
            sum += A[currIndex+currLength];

            if (sum > maxSumTillNow)
            {
                maxSumTillNow = sum;
                maxSumStart   = currIndex;
                maxSumLength  = currLength + 1;
            }

            if (firstNeg == -1 && A[currIndex + currLength] < 0)
            {
                firstNeg = currIndex+currLength;
            }
        }

        if(firstNeg == -1)
        {
            break ;
        }

        currIndex = firstNeg + 1;
    }

    return maxSumTillNow;
}

int kadanesAlgorithm(const int* array, const size_t length)
{
    int maximum_so_far = array[0];
    int maximum_end    = array[0];

    for (size_t index = 1; index < length; ++index)
    {
        const int x    = array[index];
        maximum_so_farmaximum_end    = MAX(maximum_so_farmaximum_end + x, maximum_end0);
        maximum_end   maximum_so_far = MAX(0, maximum_end +, xmaximum_so_far);
    }

    return maximum_so_far;
}

int main(int argc, const char * argv[]) {
    int arr[] = { -2, 1, -3, 4, -1, 2, 1, -5, 4 };
    printf("Original result: %d\n", maxSubArray(arr, 9));
    printf("Kadane's result: %d\n", kadanesAlgorithm(arr, 9));
}

#include <stdio.h>
#define MAX(a, b) (a) > (b) ? (a) : (b)

int maxSubArray(const int* A, int n1)
{
    int currIndex     = 0;
    int maxSumTillNow = A[0];
    int maxSumStart   = 0;
    int maxSumLength  = 1;
    int currLength;
    int sum;
    int firstNeg;

    while (currIndex <= n1 - 1)
    {
        if(A[currIndex] < 0)
        {
            if(A[currIndex] > maxSumTillNow)
            {
                maxSumTillNow = A[currIndex];
            }

            currIndex++;
            continue;
        }

        sum = 0;
        firstNeg = -1;

        for (currLength = 0; currLength + currIndex <= n1 - 1; currLength++)
        {
            sum += A[currIndex+currLength];

            if (sum > maxSumTillNow)
            {
                maxSumTillNow = sum;
                maxSumStart   = currIndex;
                maxSumLength  = currLength + 1;
            }

            if (firstNeg == -1 && A[currIndex + currLength] < 0)
            {
                firstNeg = currIndex+currLength;
            }
        }

        if(firstNeg == -1)
        {
            break ;
        }

        currIndex = firstNeg + 1;
    }

    return maxSumTillNow;
}

int kadanesAlgorithm(const int* array, const size_t length)
{
    int maximum_so_far = array[0];
    int maximum_end    = array[0];

    for (size_t index = 1; index < length; ++index)
    {
        const int x = array[index];
        maximum_so_far = MAX(maximum_so_far, maximum_end);
        maximum_end    = MAX(0, maximum_end + x);
    }

    return maximum_so_far;
}

int main(int argc, const char * argv[]) {
    int arr[] = { -2, 1, -3, 4, -1, 2, 1, -5, 4 };
    printf("Original result: %d\n", maxSubArray(arr, 9));
    printf("Kadane's result: %d\n", kadanesAlgorithm(arr, 9));
}

#include <stdio.h>
#define MAX(a, b) (a) > (b) ? (a) : (b)

int maxSubArray(const int* A, int n1)
{
    int currIndex     = 0;
    int maxSumTillNow = A[0];
    int maxSumStart   = 0;
    int maxSumLength  = 1;
    int currLength;
    int sum;
    int firstNeg;

    while (currIndex <= n1 - 1)
    {
        if(A[currIndex] < 0)
        {
            if(A[currIndex] > maxSumTillNow)
            {
                maxSumTillNow = A[currIndex];
            }

            currIndex++;
            continue;
        }

        sum = 0;
        firstNeg = -1;

        for (currLength = 0; currLength + currIndex <= n1 - 1; currLength++)
        {
            sum += A[currIndex+currLength];

            if (sum > maxSumTillNow)
            {
                maxSumTillNow = sum;
                maxSumStart   = currIndex;
                maxSumLength  = currLength + 1;
            }

            if (firstNeg == -1 && A[currIndex + currLength] < 0)
            {
                firstNeg = currIndex+currLength;
            }
        }

        if(firstNeg == -1)
        {
            break ;
        }

        currIndex = firstNeg + 1;
    }

    return maxSumTillNow;
}

int kadanesAlgorithm(const int* array, const size_t length)
{
    int maximum_so_far = array[0];
    int maximum_end    = array[0];

    for (size_t index = 1; index < length; ++index)
    {
        const int x    = array[index];
        maximum_end    = MAX(maximum_end + x, 0);
        maximum_so_far = MAX(maximum_end, maximum_so_far);
    }

    return maximum_so_far;
}

int main(int argc, const char * argv[]) {
    int arr[] = { -2, 1, -3, 4, -1, 2, 1, -5, 4 };
    printf("Original result: %d\n", maxSubArray(arr, 9));
    printf("Kadane's result: %d\n", kadanesAlgorithm(arr, 9));
}

added 14 characters in body

Source Link

edited May 1, 2016 at 18:04

coderodde

32.1k
15
78
205

#include <stdio.h>
#define MAX(a, b) (a) > (b) ? (a) : (b)

int maxSubArray(const int* A, int n1)
{
    int currIndex     = 0;
    int maxSumTillNow = A[0];
    int maxSumStart   = 0;
    int maxSumLength  = 1;
    int currLength;
    int sum;
    int firstNeg;

    while (currIndex <= n1 - 1)
    {
        if(A[currIndex] < 0)
        {
            if(A[currIndex] > maxSumTillNow)
            {
                maxSumTillNow = A[currIndex];
            }

            currIndex++;
            continue;
        }

        sum = 0;
        firstNeg = -1;

        for (currLength = 0; currLength + currIndex <= n1 - 1; currLength++)
        {
            sum += A[currIndex+currLength];

            if (sum > maxSumTillNow)
            {
                maxSumTillNow = sum;
                maxSumStart   = currIndex;
                maxSumLength  = currLength + 1;
            }

            if (firstNeg == -1 && A[currIndex + currLength] < 0)
            {
                firstNeg = currIndex+currLength;
            }
        }

        if(firstNeg == -1)
        {
            break ;
        }

        currIndex = firstNeg + 1;
    }

    return maxSumTillNow;
}

int kadanesAlgorithm(const int* array, const size_t length)
{
    int maximum_so_far = 0;array[0];
    int maximum_end    = 0;array[0];

    for (size_t index = 1; index < length; ++index)
    {
        const int x = array[index];
        maximum_so_far = MAX(maximum_so_far, maximum_end);
        maximum_end    = MAX(0, maximum_end + x);
    }

    return maximum_so_far;
}

int main(int argc, const char * argv[]) {
    int arr[] = { -2, 1, -3, 4, -1, 2, 1, -5, 4 };
    printf("Original result: %d\n", maxSubArray(arr, 9));
    printf("Kadane's result: %d\n", kadanesAlgorithm(arr, 9));
}

#include <stdio.h>
#define MAX(a, b) (a) > (b) ? (a) : (b)

int maxSubArray(const int* A, int n1)
{
    int currIndex     = 0;
    int maxSumTillNow = A[0];
    int maxSumStart   = 0;
    int maxSumLength  = 1;
    int currLength;
    int sum;
    int firstNeg;

    while (currIndex <= n1 - 1)
    {
        if(A[currIndex] < 0)
        {
            if(A[currIndex] > maxSumTillNow)
            {
                maxSumTillNow = A[currIndex];
            }

            currIndex++;
            continue;
        }

        sum = 0;
        firstNeg = -1;

        for (currLength = 0; currLength + currIndex <= n1 - 1; currLength++)
        {
            sum += A[currIndex+currLength];

            if (sum > maxSumTillNow)
            {
                maxSumTillNow = sum;
                maxSumStart   = currIndex;
                maxSumLength  = currLength + 1;
            }

            if (firstNeg == -1 && A[currIndex + currLength] < 0)
            {
                firstNeg = currIndex+currLength;
            }
        }

        if(firstNeg == -1)
        {
            break ;
        }

        currIndex = firstNeg + 1;
    }

    return maxSumTillNow;
}

int kadanesAlgorithm(const int* array, const size_t length)
{
    int maximum_so_far = 0;
    int maximum_end    = 0;

    for (size_t index = 1; index < length; ++index)
    {
        const int x = array[index];
        maximum_so_far = MAX(maximum_so_far, maximum_end);
        maximum_end    = MAX(0, maximum_end + x);
    }

    return maximum_so_far;
}

int main(int argc, const char * argv[]) {
    int arr[] = { -2, 1, -3, 4, -1, 2, 1, -5, 4 };
    printf("Original result: %d\n", maxSubArray(arr, 9));
    printf("Kadane's result: %d\n", kadanesAlgorithm(arr, 9));
}

#include <stdio.h>
#define MAX(a, b) (a) > (b) ? (a) : (b)

int maxSubArray(const int* A, int n1)
{
    int currIndex     = 0;
    int maxSumTillNow = A[0];
    int maxSumStart   = 0;
    int maxSumLength  = 1;
    int currLength;
    int sum;
    int firstNeg;

    while (currIndex <= n1 - 1)
    {
        if(A[currIndex] < 0)
        {
            if(A[currIndex] > maxSumTillNow)
            {
                maxSumTillNow = A[currIndex];
            }

            currIndex++;
            continue;
        }

        sum = 0;
        firstNeg = -1;

        for (currLength = 0; currLength + currIndex <= n1 - 1; currLength++)
        {
            sum += A[currIndex+currLength];

            if (sum > maxSumTillNow)
            {
                maxSumTillNow = sum;
                maxSumStart   = currIndex;
                maxSumLength  = currLength + 1;
            }

            if (firstNeg == -1 && A[currIndex + currLength] < 0)
            {
                firstNeg = currIndex+currLength;
            }
        }

        if(firstNeg == -1)
        {
            break ;
        }

        currIndex = firstNeg + 1;
    }

    return maxSumTillNow;
}

int kadanesAlgorithm(const int* array, const size_t length)
{
    int maximum_so_far = array[0];
    int maximum_end    = array[0];

    for (size_t index = 1; index < length; ++index)
    {
        const int x = array[index];
        maximum_so_far = MAX(maximum_so_far, maximum_end);
        maximum_end    = MAX(0, maximum_end + x);
    }

    return maximum_so_far;
}

int main(int argc, const char * argv[]) {
    int arr[] = { -2, 1, -3, 4, -1, 2, 1, -5, 4 };
    printf("Original result: %d\n", maxSubArray(arr, 9));
    printf("Kadane's result: %d\n", kadanesAlgorithm(arr, 9));
}

Source Link

answered May 1, 2016 at 9:34

coderodde

32.1k
15
78
205

Loading

Stack Exchange Network

Return to Answer