Maximum subarray problem is to find the largest contiguous sub-array which has largest sum total. For example in array {-1,-2,3,4} the largest contiguous array which has largest sum is {3,4} and the sum is 7.

simple solution with O(N²) complexity:

#include<stdio.h>

int
main ()
{
  int a[] = { -1, -2, 3, 4 };
  int n = sizeof (a) / sizeof (int);
  int i, j, sum, max;
  max = -1000;
  for (i = 0; i < n; i++)
    {
      sum = 0;
      for (j = i; j < n; j++)
	{
	  sum = sum + a[j];
	  if (sum > max)
	    max = sum;
	}
    }
  printf ("Max sum is %d \n", max);
  return 0;
}

Kadane’s Algorithm:

This algorithm works with O(N) time complexity. according to wikipedia “Kadane’s algorithm consists of a scan through the array values, computing at each position the maximum (positive sum) subarray ending at that position. This sub-array is either empty (in which case its sum is zero) or consists of one more element than the maximum sub-array ending at the previous position.” 

#include<stdio.h>

int kadane (int *a, int n)
{
  int max_ending_here = a[0], max_so_far = a[0];
  int sum = 0;
  int i;
  for (i = 1; i < n; i++)
    {
      sum = a[i] + max_ending_here;
      if (sum > a[i])
	max_ending_here = sum;
      else
	max_ending_here = a[i];

      if (max_so_far > max_ending_here)
	max_so_far = max_so_far;
      else
	max_so_far = max_ending_here;
    }
  return max_so_far;

}

int
main ()
{
  int a[] = { -1, -2, 3, 4 };
  int n = sizeof (a) / sizeof (int);
  int maxSumSubarray = kadane (a, n);
  printf ("max sumis %d \n", maxSumSubarray);
  return 0;
}

Note: Kadane’s algorithm works only when at least one positive element should be member of array. Can you modify above code to work with an array having all negative elements for example int a[] = { -1, -2, -3, -4 }. Please practice and submit code myconcept@wikistack.com.




Related Contents to follow