Program to find maximum sum subarray in C(using brust force or Kadane's algorithm ,optimal solution)

 
Program to find maximum sum subarray in C

To find maximum sum subarray two method or solution are possible first is brute force method that complexity is O(n^3).

In brute force method find all subarray then find maximum sum subarray.

For example

If array is 

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

Then subarray from this array is 

=n*(n+1)/2

=5(5+1)/2=15

So maximum subarray is 15.

{-1}      so sum=-1

{-1,2}.         Sum=1

{-1,2,3}.       Sum=4

{-1,2,3,4}.      Sum=8

{-1,2,3,4,-6}.  Sum=2

{2}.                Sum=2

{2,3}.             Sum=5

{2,3,4}.         Sum=9

{2,3,4,-6}.      Sum=3

{3}.                 Sum=3

{3,4}              sum=7

{3,4,-6}.          sum=1

{4}.                Sum=4

{4,-6}.             Sum=-2

{-6}.               Sum=-6

So maximum sum subarray is =9

Method 1.brust force method to find maximum sum subarray from array.

#include <stdio.h>

#include<math.h>

void main()

{

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

    int n=5;

    int i,j,k;

    int sum;

    int max=0;

    for(i=0;i<n;i++)

    {

        for(j=i;j<n;j++)

        {

            sum=0;

            for(k=i;k<j;k++)

            {

                sum+=a[k];

                if(sum>max)

                {

                    max=sum;

                }

                

            }

            

        }

    }

    printf("%d",max);

}

Output

9

But the complexity to find maximum sum subarray is O(n^3) because three for loop is used in the program.

Method 2: Kadane's algorithm (optimal solution to find maximum sum of subarray)

#include <stdio.h>

void main() {

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

    int n=5;

    int i;

    int sum=0;

    int max=0;

    int start=0;

    int astart=-1;

    int aend=-1;

    for(i=0;i<n;i++)

    {

        if(sum==0)

      

           start=i;

            sum=sum+a[i];

      

        if(sum>max)

        {

            max=sum;

            astart=start;

            aend=i;

           

        }

        if(sum<0)

        {

            sum=0;

        }

    }

   printf("%d",max);

}

Output 

9.

To find maximum sum subarray using Kadane's algorithm complexity is O(n) .so Kadane's is optimal solution to find maximum sum subarray as compare to brute force method that complexity is O (n^3).