Largest sum contiguous subarray - Kadane's Algorithm

Variation 1: Kadane Algo. for 1d Array/ Maximum Sum of All Sub-arrays
Write an efficient C program to find the sum of contiguous subarray within a one-dimensional array of numbers which has the largest sum. Also find the subarray.

http://www.programcreek.com/2013/02/leetcode-maximum-subarray-java/
http://www.geeksforgeeks.org/largest-sum-contiguous-subarray/
http://codercareer.blogspot.in/2011/09/no-03-maximum-sum-of-all-sub-arrays.html

Variation 2: Maximum subset [ Not Sub-array ] sum Problem.
Given a set of non-negative integers, and a value sum, determine if there is a subset of the given set with sum equal to given sum.
http://www.geeksforgeeks.org/dynamic-programming-subset-sum-problem/
http://www.ideserve.co.in/learn/subset-sum-dynamic-programming

Variation 3:  Largest Sum Contiguous Subarray for 2D array.
Given a 2D array, find the maximum sum subarray in it.
http://www.geeksforgeeks.org/dynamic-programming-set-27-max-sum-rectangle-in-a-2d-matrix/

Variation 4: Maximum circular subarray sum
n numbers (both +ve and -ve) are arranged in a circle. find the maximum sum of consecutive nos. Do this in O(n) time

E.g.: {8,-8,9,-9,10,-11,12}
max = 22 (12 + 8 - 8 + 9 - 9 + 10)
http://www.geeksforgeeks.org/maximum-contiguous-circular-sum/

Variation 6: Maximum Product Subarray
Also, Given an array of integers (possibly some of the elements negative), write a C program to find out the *maximum product* possible by adding 'n' consecutive integers in the array, n <= ARRAY_SIZE. Also give where in the array this sequence of n integers starts.
http://www.programcreek.com/2014/03/leetcode-maximum-product-subarray-java/
http://www.geeksforgeeks.org/maximum-product-subarray/

Method 1:

Kadanes Algorithm:

We will use a scanning algorithm using two pointers.
Pointer A stays at 0 and pointer B starts scanning ahead.
Calculate the sum at every step of B and compare with the max sum found so far.
Maintain the max sum pointer position (of B) and the max sum found so far.
When the sum hits negative or zero, bring Pointer A to the current position and restart the scanning using pointer B. O(n)


Code:

int maxSubArraySum(int a[], int size)

{

   int max_so_far = 0, max_ending_here = 0;

   int i;

   for(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;

}

Time:O(n)

For int a[] = {-2, -3, 4, -1, -2, 1, 5, -3};the answer comes as 7

E.g.: {8,-8,9,-9,10,-11,12}
max = 22 (12 + 8 - 8 + 9 - 9 + 10)
 
To get indexes of subarray
#include <stdio.h>
#include <stdlib.h>

int maxSubArraySum(int a[], int size,int *begin,int *end)
{
   int max_so_far = 0, max_ending_here = 0;
   int i,current_index = 0;
 
   for(i = 0; i < size; i++)
   {
     max_ending_here = max_ending_here + a[i];
   
     if(max_ending_here <= 0)
        {
         max_ending_here = 0;
         current_index=i+1;
        }
     else if (max_so_far < max_ending_here)
         {
          max_so_far = max_ending_here;
          *begin = current_index;
          *end=i;
          }
   }
   return max_so_far;
}

int main()
{
  int arr[] = {6,-5,7,9,-4,-3,5,-6};
  //int arr[] = {5,2,-1,-2,-4,3,5,-6};
  int begin=0,end=0;
  int size=sizeof(arr)/sizeof(arr[0]);

  printf(" The max sum is %d",maxSubArraySum(arr,size,&begin,&end));
  printf(" The begin and End are %d & %d",begin,end);
  getchar();
  return 0;
}

Method 2:

Use divide n conquer. Divide the problem into two, compare best case of left, right and maximum subset at the junction.
For checking the maximum subset at the junction, we have to get maximum subset at the corners and merge them. The complexity of this approach will be nlogn.

Method 3:

First, you can convert the list into a list of cumulative sums, turning [5,-2,10,-4] into [0,5,3,13,9]. Then walk through the list of cumulative sums, to get the maximum positive difference. If minimum lies before the maximum in the cumulative sum, then that is the answer. For example, minimum here is 0 and maximum is 13. The answers will be numbers contributing towards it [5,-2, 10]
The gist of the concept is to get the maximum positive delta.