Largest continuous sub array problem

April 22, 2016

 Buy and sell stock - Leetcode question

http://www.geeksforgeeks.org/largest-sum-contiguous-subarray/

It is Dynamic programming problem.

Check Kadane's algorithm:

Question and Answer Time:
Question: What do you learn through the study?
Answer: This is a dynamic programming problem. Use two variables to track the statistics:
One is called maximum value ending here. max_ending_here;
Another one is called maximum value so far. max_so_far.

Let us walk through the code:

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;

}

Handle the case when all numbers in the array are negative:

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;

}