Largest Sum Contiguous Subarray

CODE

Largest Sum Contiguous Subarray

Write an efficient program to find the sum of contiguous subarray within a one-dimensional array of numbers which has the largest sum.

Method 1:-

// C++ program to print largest contiguous array sum

#include<iostream>

#include<climits>

using namespace std;

int maxSubArraySum(int a[], int size)

{

    int max_so_far = INT_MIN, max_ending_here = 0;

    for (int i = 0; i < size; i++)

    {

        max_ending_here = max_ending_here + a[i];

        if (max_so_far < max_ending_here)

            max_so_far = max_ending_here;

        if (max_ending_here < 0)

            max_ending_here = 0;

    }

    return max_so_far;

}   

/*Driver program to test maxSubArraySum*/

int main()

{

    int a[] = {-7, -3, 4, -1, -7, 1, 5, -3};

    int n = sizeof(a)/sizeof(a[0]);

    int max_sum = maxSubArraySum(a, n);

    cout << "Maximum contiguous sum is " << max_sum;

    return 0;

}

Output:

Maximum contiguous sum is 7

Method 2:-

int maxSubArraySum(int a[], int size)

{

   int max_so_far = 0, max_ending_here = 0;

   for (int i = 0; i < size; i++)

   {

       max_ending_here = max_ending_here + a[i];

       if (max_ending_here < 0)

           max_ending_here = 0;

       /* Do not compare for all elements. Compare only   

          when  max_ending_here > 0 */

       else if (max_so_far < max_ending_here)

           max_so_far = max_ending_here;

   }

   return max_so_far;

}

Method 3:-

#include<iostream>

using namespace std;   

int maxSubArraySum(int a[], int size)

{

   int max_so_far = a[0];

   int curr_max = a[0];

   for (int i = 1; i < size; i++)

   {

        curr_max = max(a[i], curr_max+a[i]);

        max_so_far = max(max_so_far, curr_max);

   }

   return max_so_far;

}

/* Driver program to test maxSubArraySum */

int main()

{

   int a[] =  {-7, -3, 4, -1, -7, 1, 5, -3};

   int n = sizeof(a)/sizeof(a[0]);

   int max_sum = maxSubArraySum(a, n);

   cout << "Maximum contiguous sum is " << max_sum;

   return 0;

}

Output:

Maximum contiguous sum is 7

Method 4:-

// C++ program to print largest contiguous array sum

#include<iostream>

#include<climits>

using namespace std;   

int maxSubArraySum(int a[], int size)

{

    int max_so_far = INT_MIN, max_ending_here = 0,

       start =0, end = 0, s=0;

    for (int i=0; i< size; i++ )

    {

        max_ending_here += a[i];

        if (max_so_far < max_ending_here)

        {

            max_so_far = max_ending_here;

            start = s;

            end = i;

        }

        if (max_ending_here < 0)

        {

            max_ending_here = 0;

            s = i + 1;

        }

    }

    cout << "Maximum contiguous sum is "

        << max_so_far << endl;

    cout << "Starting index "<< start

        << endl << "Ending index "<< end << endl;

}

/*Driver program to test maxSubArraySum*/

int main()

{

    int a[] = {-7, -3, 4, -1, -7, 1, 5, -3};

    int n = sizeof(a)/sizeof(a[0]);

    int max_sum = maxSubArraySum(a, n);

    return 0;

}

Output:

Maximum contiguous sum is 7

Starting index 2

Ending index 6