Monday, September 20, 2010

Maximum contiguous sum in an array

Given an array of integers find the contiguos sequence with maximum sum
Pubblicato da a
Reazioni: 

3 comments:

  1. Here is an excellent blog post on this topic http://wordaligned.org/articles/the-maximum-subsequence-problem

    ReplyDelete

  2. The solution could be:

    int vect[] = {1,1,2,1,1,1,1,3,3,3,2};

    int cont_seq_sum(int vect[], int size)
    {
    int sum = vect[0];
    int max = sum;
    for (int i=0; i max )
    max = sum;
    }
    return max;
    }

    int main( int argc, char* argv[] )
    {
    std::cout << max_cont_seq(vect,sizeof(vect)/sizeof(int)) << std::endl;
    std::cout << cont_seq_sum(vect,sizeof(vect)/sizeof(int)) << std::endl;
    return 0;
    }

    ReplyDelete

  3. I guess you contented in reading the book Programming Pearls by Bentley. One column was dedicated to this algorithm. I am providing the code.

    int max_subarray_kadane_algo(int array[], int size)
    {
    int max_sofar = 0;
    int max_ending_here = 0;
    int index;

    for(index = 0; index < size; index++)
    {
    max_ending_here = max(0, max_ending_here + array[index]);
    max_sofar = max(max_sofar, max_ending_here);

    // Visulise the algorithm
    cout << "Element " << array[index] << endl;
    cout << "max_ending_here " << max_ending_here << endl;
    cout << "max_sofar " << max_sofar << endl << endl;
    }

    return max_sofar;
    }

    int main()
    {
    // Exercise problem from Algorigthms by Das Gupta
    int data[] = {5, 15, -30, 10, -5, 40, 10};

    int size = sizeof(data)/sizeof(data[0]);

    cout << "Result " << max_subarray_kadane_algo(data, size);
    }

    ReplyDelete

Subscribe to: Post Comments (Atom)